[LeetCode] 1. Two Sum (JAVA)

문제

• 문제 링크

고민 했던 상황

배열 안에서 어떻게 해야 짝을 찾을 수 있을까? i,j 를 써서 j는 난수 인덱스로 지정해서 target 에 맞춰야하나? 라고 생각했었다

나의 코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int sum = 0;

        int[] result = new int[2];

        for(int i = 0; i < nums.length; i++){
            for(int j = i+1; j < nums.length; j++){
                sum = nums[i] + nums[j];

                if(sum == target){
                    result[0] = i;
                    result[1] = j;

                    return result; //반복문 조기 종료를 위해서
                }
            }
        }
        return result;
    }
}

최선의 경우: O(1)
예: nums[0] + nums[1]이 바로 target인 경우

최악의 경우: O(n²)
예: 정답이 맨 마지막 조합에 있거나, 거의 끝까지 탐색해야 하는 경우

평균적으로도: O(n²)

다른 사람들의 코드와 비교했을 때 딱히 좋은 성능은 아니였다.

• 다른 사람들의 코드는 HashMap을 사용해서 구현했기 때문이다

---

다른 코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                return new int[]{map.get(nums[i]), i};
            }

            map.put(target - nums[i], i);
        }

        return new int[]{-1, -1};
    }
}

핵심 아이디어

현재 숫자를 봤을 때, 이 숫자를 필요로 했던 이전 숫자가 있었는지 확인한다.

예를 들어 target = 9이고 현재 숫자가 2라면, 2와 더해서 9가 되려면 7이 필요하다.

target - nums[i]

즉, 9-2 = 7 이므로 7이 나중에 나오면 현재 숫자 2와 짝이 될 수 있다.

그래서 HashMap에는 현재 숫자 자체를 저장하는 것이 아니라, 앞으로 필요한 숫자를 key로 저장한다.

map.put(target - nums[i], i);

여기서 의미는 다음과 같다.

key   : 앞으로 필요한 숫자
value : 그 숫자를 필요로 하는 현재 인덱스