LeetCode 1. Two Sum

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

 

 

Array 활용 문제

난이도 : easy

 

* IT's LIT 1주차

class Array {

    // Runtime: 48 ms, Memory: 42.9 MB
    public static int[] twoSum(int[] nums, int target) {
        int[] ret = new int[2];
        for(int i=0; i<nums.length; i++){
            for(int j=i+1; j<nums.length; j++){
                if (nums[i]+nums[j] == target) {
                    ret[0] = i;
                    ret[1] = j;
                }
            }
        }
        return ret;
    }
    
}

 

 

 

남들 Solutions 보고 다시 푼 것

class Array {

    // Runtime: 1ms, Memory: 42.8 MB
    public static int[] twoSum_again(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = target - nums[i];
            if (map.containsKey(num)) {
                return new int[]{map.get(num), i};
            } else {
                map.put(nums[i], i);
            }
        }
        return null;
    }

}

 

array의 요소 하나씩 for문 돌리면서
해당 값이 target이 되기 위한 정답값을 찾아서 map에 넣고
for문 돌때마다 map에 해당 값이 있는지 찾기
이로써 반복문이 한번만 돌게 되어 실행시간 단축됨

map은 엄청 빠르구나 느낌