[leetcode] 15. 3Sum

문제

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

 

풀이

숫자 $nums[i]$를 하나 고르고, 구간 $[i+1, l)$에서 합이 $-nums[i]$인 쌍 $(j,k)$를 구하면 된다.

Container With Most Water문제와 비슷하게 하나의 $nums[i]$에 대해서는 양쪽에서 범위를 좁혀가면서 구한다.

 

$sum=nums[i]+nums[j]+nums[k]$의 부호에 따라서 경우가 나뉘게 된다.

case 1) $sum>0$

$num[k]$가 너무 큰 것이므로, k를 1 감소시킨다.

 

case 2) $sum<0$

$num[j]$가 너무 작은 것이므로, j를 1 증가시킨다.

 

case 3) $sum=0$

해답을 찾았다. 현재의 {$nums[i], nums[j], nums[k]$}를 정답 vector에 추가해준다.

중복을 제거하기 위해서, 현재 $nums$값과 다른 새로운 값이 나올때 까지 j값을 증가시켜준다.

현재 j에 대한 $sum$은 양수이므로, 같은 방법으로 새로운 값이 나올때 까지 k값을 감소시켜준다.

 

이러한 방법으로 특정 i에 대해서 $nums[j]$와 $nums[k]$의 순서쌍을 $O(n)$만에 구할 수 있다.

또한 i가 총 $O(n)$개 존재하므로, 시간복잡도는 $O(n^2)$이다.

 

Time Complexity : $O(n^2)$

코드

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &nums) {
        vector<vector<int> > ret;
        sort(nums.begin(), nums.end());
        int l = nums.size();
        for (int i=0;i<l-2;i++)
        {
            int j=i+1, k=l-1;
            while(j<k)
            {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum > 0){k--; continue;}
                if (sum < 0){j++; continue;}
                
                ret.push_back({nums[i],nums[j],nums[k]});
                while(j<l-1 && nums[j+1]==nums[j]) j++;
                while(k>0 && nums[k-1]==nums[j]) k--;
                j++;k--;
            }
            while(i<l-1 && nums[i+1]==nums[i]) i++;
        }
        return ret;
    }
};