[HashMap] Two Sum

1. 문제

LeetCode - Two Sum

• 정수형 배열 nums와 목표 target이 주어졌을 때, 더해서 target과 같아지는 nums 요소의 인덱스를 반환하는 문제
• 각 입력에는 정확히 하나의 솔루션이 있다고 가정할 수 있으며, 동일한 요소를 두 번 사용할 수 없다고 한다.

2. 접근법

• 가장 먼저 떠오르는 방법은 더해서 target을 만족하는 요소들의 인덱스로 구성된 배열을 map에 value로 저장하고, 반복문을 돌다가 key로 target이 존재하면 반환하는 것 -> 성공
• 그러나, 단순 이중 반복문 해결법이다 보니 runtime 성능이 너무 느리게 나옴
• 반복문 하나로 해결하는 방법으로 성능 개선(328ms -> 2ms)

3. 코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 1. target을 key로, 더해서 target이 되는 요소의 인덱스 배열을 value로
        Map<Integer, int[]> map = new HashMap<>();

        // 2. 이중 반복문을 돌면서 target을 만족하는 요소를 찾는다
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                // 2-1. 더해서 target과 같다면 map에 인덱스 배열로 저장
                if (nums[i] + nums[j] == target) {
                    map.put(target, new int[]{i, j});
                }
                // 2-2. target이 map에 있으면 value를 반환
                if (map.containsKey(target)) {
                    return map.get(target);
                }
            }
        }
        // 3. 없으면 빈 배열 리턴
        return new int[]{};
    }
}

4. 성능

- Runtime : 328ms -> 2ms

- Memory : 44.2mb -> 43.9mb

5. 개선

• Map의 value 타입 및 저장하는 요소 변경
• 기존: target을 key로, 더해서 target이 되는 요소의 인덱스 배열을 value로 했다면
• 개선: 요소를 key로, 해당 요소의 인덱스를 value로 설정
• 하나의 반복문으로 해결 가능

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 1. nums의 요소를 key로, 해당 요소의 인덱스를 value로 저장
        Map<Integer, Integer> map = new HashMap<>();

        // 2. nums를 순회하면서 map을 업데이트
        for (int i = 0; i < nums.length; i++) {
            // target에서 현재 인덱스의 요소를 뺀 값
            int complement = target - nums[i];
            // map에 해당 값이 있다면(즉, 더해서 target이 되므로)
            if (map.containsKey(complement)) {
                // 해당 값의 인덱스와 현재 인덱스로 이루어진 배열 반환
                return new int[]{map.get(complement), i};
            }

            // 아직 찾지 못했으므로, map에 요소와 인덱스를 저장
            map.put(nums[i], i);
        }

        // 3. 없으면 빈 배열 리턴
        return new int[]{};
    }
}