[LeetCode] 3Sum

Url: https://leetcode.com/problems/3sum/description/

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

n개의 S배열에서 a + b + c = 0인 배열을 찾는 문제. Brute Fource로 3중 루프 돌려서 처리할 수도 있고, 사실 정답이란게 없어서 그게 답인 것 같기도 하고 애매모호하지만..

처음에는 포인터 2개 써다가 n만에 해보려고 시도했었다. 일단 해시테이블에 모두 넣고, low, high 로 왼->오, 오->왼 으로 훑으며 (a[low] + a[high]) * -1 이 해시에 있나 체크해서 있으면 결과에 넣는 방식으로. 허나 이 경우에는 일단 중복값이 발생할 수 있고, 어쨌거나 코드가 정렬되지 않았으므려 정렬에 O(nlogn)이 소요되고, 코드가 복잡해지는 경향을 보였다.

일단 처음에 생각해 봐야 할 것은 2Sum을 어떻게 처리했느냐이다. 물론 2Sum을 처리하는 방법에는 해시맵을 쓰는게 가장 좋긴 한데 (이 경우 n만에 답이 나옴), 포인터를 두개 두고 처리할 수도 있다.  즉, 일단 정렬을 해두고 처음(low)과 끝(high)의 두 개의 포인터로 내려가며, 해당 합이 k보다 작으면 low를 증가시키고, 크면 high를 감소시키면서 처리. 이 경우 n번만 스캔을 하게 된다.

3Sum을 결과적으로 내가 찾은 답은, 모든 원소에 대해 해당 원소의 음수 값이 다른 원소 사이에서 위의 2Sum의 결과가 존재하느냐를 찾으면 되는 것이다. 2Sum문제 자체에서, a + b = -c의 경우만 찾으면 된다. 즉, a[j] + a[k] = a [i] * -1 (i = 0…n-1, j = (i+1)…n-1, k = n-1…(i+1), j < k) 의 간단한 알고리즘으로 추려진다.

class Solution {
    
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> rslt = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for(int i = 0 ; i < nums.length ; i++){ if(i == 0 || (i > 0 && nums[i-1] != nums[i])){
                int low = i+1;
                int high = nums.length - 1;
                int sum = nums[i] * -1;
                while(low < high){
                    if(nums[low] + nums[high] == sum){
                        rslt.add(Arrays.asList(nums[i], nums[low], nums[high]));
                        while(low < high && nums[low] == nums[low+1])   low++;
                        while(low < high && nums[high] == nums[high-1]) high--;
                        low++;
                        high--;
                    }else if(nums[low] + nums[high] < sum){
                        while(low < high && nums[low] == nums[low+1])   low++;
                        low++;
                    }else{
                        while(low < high && nums[high] == nums[high-1]) high--;
                        high--;
                    }
                }
            }
        }
        
        return rslt;
    }
}

시간복잡도: O(n^2)