[알고리즘] Two Sum

문제 정보

출처 : leetcode
난이도 : easy

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]

내 풀이

알고리즘 : 부르트포스 알고리즘
시간복잡도 : O(n^2)
공간복잡도 : O(1)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int sum = nums[i] + nums[j];
                if (sum == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }
}

이렇게 생각한 이유는 두 수의 합이 target이면 return하는 거여서, 전체를 다 더해보고 정답이 나오면 return하면 된다고 생각했다.

runtime : 45 ms
memory : 43.9 MB

개선하기

letcode에 나온 강의를 듣고 개선한 방법이다.
알고리즘 : One-pass Hash Table (정확힌 모르겠으나 for문을 하나 쓴 HashTable인듯)
시간복잡도 : O(n)
공간복잡도 : O(n)

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;
    }
}

Map에 nums값들을 넣고,
nums[i] + x = target인 값을 찾아야하니까
x = target - nums[i]로 치환해서 x의 값을 map에서 찾아내는 것입니다.

Map에서 값을 찾는 것은 시간복잡도가 O(1)이여서, Map을 사용하면 해당 알고리즘의 시간복잡도는 O(n^2)에서 O(n)으로 줄어든다.

runtime : 2 ms
memory : 43.7 MB

개선한 대로 풀면 memory는 별 차이 없지만 runtime이 확실하게 줄어든 것을 볼 수 있다.