1. Two Sum

문제 링크: https://leetcode.com/problems/two-sum/

이 포스팅을 작성하는 이유는 3Sum과 4Sum 문제를 풀기 위해서다.
이 문제는 배열이 주어지고, 합이 target이 되는 원소 2개의 index를 반환하는 문제이다.

Solution

1. Brute Force

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++) {
                if(nums[i]+nums[j] == target) return new int[] {i, j};
            }
        }
        return new int[] {};
    }
}

최악의 경우 O(N^2)의 시간복잡도를 가진다. 설명은... 생략

2. Two-pass Hash Table

여기서부터 3Sum과 4Sum 문제를 푸는 발판이 되는 해결방법이다.
HashMap을 사용하는데, 각 원소와 그 인덱스를 HashMap에 넣어둔 후, complement가 있는지 O(1)로 검색하는 방법이다. (HashMap에서의 원소 검색은 충돌이 일어나지 않는 한 O(1), 충돌이 일어나는 경우 O(N))

• 1st iteration) HashMap에 <원소, index>를 넣는다.
• 2nd iteration) HashMap에서 현 원소의 complement(target-num)이 있는지 찾고, 있다면 바로 그 index로 배열을 만들어 반환한다.

주의할 점 map.get(complement)!=i
같은 원소를 중복으로 사용하면 안 되므로, 검색한 complement가 자기 자신이 아닌지 검사해야 한다!

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<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++) {
            int complement = target-nums[i];
            if(map.containsKey(complement) && map.get(complement)!=i) 
                return new int[] {map.get(complement), i};
        }
        return new int[] {};
    }
}

3. One-pass Hash Table

2번 방법을 개선한 방법인데, HashMap에 <원소, index>를 넣으면서 complement가 있는지 O(1)로 검색하는 방법이다. 총 1회의 iteration이 소요되고, O(N)의 시간복잡도를 가진다.

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