Grind 75: Two Sum

[sonic247897]

O(n^2) 풀이법

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = i + 1; j < nums.size(); ++j) {
                if (nums[i] + nums[j] == target) {
                    return vector<int> { i, j };
                }
            }
        }
        return vector<int> { -1 };
    }
};

O(n^2) 보다 낮은 시간 복잡도로 풀려면?

1. CS 배경지식

   • 배열은 메모리상 1차원 연속 공간에 저장됨
   • 배열 정렬 알고리즘 중에 가장 낮은 시간 복잡도를 가지는 병합정렬이나 힙정렬은 O(nlogn) 복잡도를 가진다.
   • 정렬된 배열에 대해서 탐색하는 알고리즘 중에 가장 낮은 시간 복잡도를 가진 이진 탐색 알고리즘은 O(logn) 복잡도를 가진다.

2. 수학적으로는 target보다 더 큰 원소들에 대해서는 탐색할 필요가 없다.

=> 위 두 가지 사실을 이용해서 1) {원소, index} 쌍을 저장하는 자료구조를 만들고, 2) 원소를 기준으로 오름차순으로 O(nlogn) 복잡도로 정렬한 다음, 3) 정렬된 배열에 대해서 이진 탐색으로 target보다 큰 원소는 탐색 범위에서 제외함.

그런데 이진 탐색 알고리즘으로 two sum을 찾을수 있나?? 복잡도만 기억나서 더 이상 분석이 어렵다.

[hotpineapple]

O(n) 풀이

1. 아이디어
   • 원소 별로 값이 ${target-원소의 값}인 다른 원소를 찾기위해 n이 아니라 1의 시간을 가지도록 하는 것
2. 구현
   • map을 이용
     3. 코드

        class Solution {
        public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i =0 ;i < nums.length; i++) {
        map.put(nums[i], i);
        } 
        for (int i = 0; i < nums.length; i++) {
        if (map.contains(target - nums[i)) > -1 && map.get(target - nums[i]) != i ) return new int[]{ i, map.get(target - nums[i]) };
        }
        return new int[]{};
        }
        }

[0tak2]

O(n^2) 풀이

• 완전 순회
• 모든 페어에 대해, 더해서 target이 되는지 검사

// 69ms, 43.73MB
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i == j) {
                    continue;
                }

                if (nums[i] + nums[j] == target) {
                    result[0] = i;
                    result[1] = j;
                    break;
                }
            }
        }

        return result;
    }
}

O(n) 풀이

• 지혜님 아이디어 참고, Map 이용
• 순회할 때마다 Map에 Value와 Index를 기록

// 2ms, 45.14MB
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<>(); // value: index

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int foundIndex = map.getOrDefault(target - num, -1);
            if (foundIndex >= 0) {
                result[0] = i;
                result[1] = foundIndex;
                break;
            }

            map.put(num, i);
        }

        return result;
    }
}

// 0ms, 5.77MB, 100%
func twoSum(nums []int, target int) []int {
    memo := map[int]int {}

    for i:=0; i < len(nums); i++ {
        foundIndex, exists := memo[target - nums[i]]
        if exists {
            return []int{i, foundIndex}
        }
        memo[nums[i]] = i
    }

    return []int{}
}