Two sum

들어가는 말

Leetcode를 시작하고 처음 풀어본 문제 Two sum.
정수형 배열 nums가 주어지고 정수 target가 주어졌을 때, nums의 두 요소의 합으로 target을 만들 수 있는 인덱스를 배열로 넣어 구하는 문제다.

초기 코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];

        for(int i=0; i<nums.length-1; i++){
            for(int j=i+1; j<nums.length; j++){
                if(nums[i] + nums[j] == target){
                    answer[0] = i;
                    answer[1] = j;
                    break;
                }
            }
        }

        return answer;
    }
}

그냥 보자마자 이중반복문으로 푸는 걸 생각했다. 이렇게 되면 시간 복잡도는 O(n^2)이다. 답은 나오지만 Runtime 통계에서 보듯이 느리다. 그렇다면 시간을 줄이기 위해서 어떻게 해야 할까.

수정 코드

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

        for(int i=0; i<nums.length; i++){
            int cur = nums[i];
            int x = target - cur;

            if(map.containsKey(x)){
                return new int[] {map.get(x), i};
            }

            map.put(cur, i);
        }

        return null;
    }
        
}

공식 솔루션을 보면 HashMap와 target은 두 원소의 합이라는 점을 이용했다. 'target = num[i] + num[j]'이니 num[i]를 cur, num[j]를 x라고 한다면 'x = target - cur'이 된다. 그리고 map을 이용해 각 배열의 값을 key로 인덱스를 value로 저장해서 만일 x의 값이 존재한다면 배열에 넣어 return하고 아니면 map에 각각의 값을 넣는다. 이렇게 하면 공간 복잡도는 좀 늘어날지라도 시간 복잡도는 O(n)으로 줄어든다.