[LeetCode] 1. Two Sum

■ 문제

문제

배열에서 요소 2개를 더했을 때 target 이 나오는 인덱스를 구하는 문제이다.

 

■ 풀이

현재 문제에서는 시간제한이 딱히 명시되어 있지 않다.

실제로 브루트포스 알고리즘을 써서 완전탐색을 해도 풀이는 가능하다.

 

하지만 실제 코테에서는 완전탐색으로 풀 수 있는 Constraints 의 문제가 나오지 않을 것 같아 다른 방법을 생각해보느라 시간이 좀 걸렸다.

 

a + b = target 이 나오는 공식에서 해결이 가능한 미지수는 a 또는 b 와 target 이다.

[2, 7, 11, 15] 를 예시로 들어봤을 때 index = 0 일 경우, 2+b = 9 이다.

 

즉, 단순 for 순회에서 9-2 인 값을 O(1) 로 찾을 수 있는 설계를 하면 된다.

이를 위해 HashMap 을 사용했다.

1. for 문을 돌며 HashMap 에 {value : index} 로 저장한다
2. 다시 for 문을 돌며 target - nums[i] 를 통해 예상되는 b 값을 찾는다.
3. b 가 HashMap 에 Key로 존재하는지 조회하면 a, b를 찾을 수 있다.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] answers = new int[2];
        int size = nums.length;
        HashMap<Integer, Integer> hm = new HashMap<>();
        
        for(int i=0; i<size; i++){
            hm.put(nums[i], i);
        } 

        for(int i=0; i<size; i++){
            int diff = target - nums[i];
            if(hm.containsKey(diff) && hm.get(diff) != i){
                return new int[]{i, hm.get(diff)};
            }
        }

        return answers;
    }
}

 

hm.get(diff) != i 는 중복되는 요소들을 해결하기 위함이다.

예를 들어 [3, 6, 3] 이고 target 이 6일 때, 인덱스를 구분하지 않으면 [2,2] 로 반환 될 것이다.