[Leetcode/Hashmap] Two sum (feat. Java)

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

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];
        HashMap<Integer, Integer> hm = new HashMap<>();
        
        for(int i = 0; i < nums.length; i++){
            int complement = target - nums[i];
            if(hm.containsKey(complement)) {
                answer[0] = i;
                answer[1] = hm.get(complement);
            } else {
                hm.put(nums[i], i);
            }
        }

        return answer;
    }
}

해시테이블에 element와 인덱스를 저장해놓으면 brute force로 반복문 두번 돌 것을 한 번만에 해결할 수 있다.

예를 들어 nums = [2, 3, 4, 5] , target = 8 인 경우

- 1 iteration 

complement = 8 - 2 = 6 이고, hm이 비어있으므로 else문을 타서 {2, 0} 을 저장한다.

- 2 iteration

complement = 8 - 3 = 5 이고, hm의 키에 6이 없으므로 else문을 타서 {3, 1} 을 저장한다.

- 3 iteration

complement = 8 - 4 = 4 이고, hm의 키에 4가 없으므로 else문을 타서 {4, 2} 을 저장한다.

- 4 iteration

complement = 8 - 5 = 3 이고, hm.get(3) = 1 이므로

{현재 반복하고 있는 인덱스, hm에 저장되어있는 complement 의 value index} 즉, {3, 1} 을 리턴한다.

 

이미 지난것에 대해 저장을 해왔기 때문에 이중 루프를 타면서 하나하나 다 살펴볼 필요가 없게된다.

시간이 brute force에 비해 매우 단축된다.