15. 3Sum

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

Two Sum 과 Two Sum II 문제에 이어지는 문제이다.
배열이 주어지고, 합이 0이 되는 세 원소쌍들을 모두 찾아 반환하는 문제이다.

문제 풀이에 들어가기 전에, Two Sum 문제를 해결한 방법을 살펴보면,

• Two Sum은 complement 값을 찾기 위해 HashMap을 사용했다. 따라서 O(N)의 시간 복잡도를 가진다.
• Two Sum II는 정렬된 배열에서의 two pointers pattern을 사용했고, 정렬하는데에 필요한 O(NlogN)의 시간복잡도를 가진다.

3 Sum은 Two Sum에서 문제공간이 한 차원 더 추가 됐으므로, O(N^2)의 시간복잡도를 가질 것이라 추정한다.

Solution

1. Two Pointers approach

Two Sum II 풀이와 같이 two pointers 패턴을 적용해 풀어보려고 한다. 먼저 input 배열의 정렬이 필요하다.

알고리즘

1. input 배열 정렬시키기
   result가 unique한 triplets만을 포함시키도록, 중복된 원소를 skip하는 부분이 필요하다. 배열이 이미 정렬되어있으니 수월할 것이다.
   (1) if(i!=0 && nums[i] == nums[i-1]) continue;
   (2) while(lo<hi && nums[lo] == nums[lo-1]) lo++;

2. pivot 원소를 선택, 합이 -pivot이 되는 두 원소 찾기

• 만약 pivot 원소가 양수라면, 두 원소의 합이 음수가 될 수 없으므로 iteration을 중단한다.
• Two Sum 풀이에서와 같이 complement를 이용할 것이다.
  → 세 원소의 합이 0이어야 하니, pivot 원소를 고르고, 합이 -pivot이 되는 두 원소를 찾는다.
  이 때 Two Sum II 풀이와 같이 two pointers 패턴을 이용해 num[lo]+num[hi] == target일 때까지 iteration을 수행한다.
  (two pointers pattern: 두 포인터는 각각 input배열의 첫번째 원소와 마지막 원소를 가리키고 있다. 두 원소의 합이 target과 같아질 때까지 이진탐색을 수행한다. target과 합이 같으면 반환하고, 합이 target보다 크면 오른쪽 포인터를 왼쪽으로 옮기며, 그 반대의 경우엔 왼쪽 포인터를 오른쪽으로 옮긴다.)

3. result를 반환한다.

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    
    public void twoSum(int[] nums, int pivot, int pivotIndex) {
        int lo=pivotIndex+1; 
        int hi=nums.length-1;
        int target = pivot*(-1);
        
        int sum;
        while(lo<hi) {
            sum = nums[lo]+nums[hi];
            if(sum == target) {
                res.add(Arrays.asList(pivot, nums[lo++], nums[hi--]));
                while(lo<hi && nums[lo] == nums[lo-1]) lo++;
            }
            else if(sum < target) lo++;
            else hi--;
        }
        
    }
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        
        int pivot;
        for(int i=0; i<nums.length && nums[i]<=0; i++) {
            if(i!=0 && nums[i] == nums[i-1]) continue;
            pivot = nums[i];
            twoSum(nums, pivot, i);
        }
        return res;
    }
}

2. HashSet

세 원소쌍의 합이 target이 되어야 하니, Two Sum 풀이에서와 같이 HashSet을 이용할 수 있다.
pivot 원소 nums[i]를 정하고, HashSet을 이용해 합이 -nums[i]가 되는 두 원소를 찾는다.

1. nums[j]를 pivot 오른쪽에서부터 차례로 이동시키며,
   -nums[i]-nums[j]인 원소가 HashSet에 있는지 확인한다.

2. 원소가 존재한다면, 세 원소쌍을 찾은 것이다.

3. nums[j]를 HashSet에 삽입한다.

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        for(int i=0; i<nums.length-1 && nums[i]<=0; i++) {
            if(i!=0 && nums[i-1]==nums[i]) continue;
            twoSum(nums, i);
        }
        return list;
    }
    
    public void twoSum(int[] nums, int i) {
        Set<Integer> set = new HashSet<Integer>();  
        
        for(int j=i+1; j<nums.length; j++) {
            int complement = -nums[i] - nums[j];
            if(set.contains(complement)) {
                list.add(Arrays.asList(complement, nums[i], nums[j]));
                while(j<nums.length-1 && nums[j] == nums[j+1]) 
                    j++;
            }
            set.add(nums[j]);
        }
    }
    
}