[C++] LeetCode : 3sum

Question

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

 

Notice that the solution set must not contain duplicate triplets.

 

integer 변수로 이루어진 배열 nums 가 주어질 때 i != j, i != k,  j != k 이고 nums[i] + nums[j] + nums[k] == 0 인 모든 세 쌍 [nums[i], nums[j], nums[k]] 을 return 하라
 
제약사항

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

• 모든 숫자를 한번씩은 살펴봐야 하기 때문에 O(n) 이다.

Solution1 (Bruth Force)

루프를 세 번 돌아 해당식을 만족하는 경우의 수를 모두 찾고, 중복된 부분을 제외한다. O(n^3) 
3x10³ 의 3중 루프면 27*10^9 계산이기 때문에 시간이 오래 걸린다.

Solution2

잘 생각해보면 세 수가 모두 양수인 경우 혹은 음수인 경우 고려할 필요가 없다. 이를 적용하기 위해 정렬을 한번 해준다. O(nlogn)

[-1, 0, 1, 2, -1, -4] 배열이 있다고 할 때 이를 정렬하면 
[-4,-1,-1, 0,  1,  2] 이다.

수가 배치된 형태를 보면 한 숫자를 기준으로 잡고 2개의 포인터를 둔 후  합이 0이 만족하는지를 판단할 수 있을 것 같다. 
중복을 걸러내기 위해 Set을 사용한다. 정렬이 되지 않을 수 있을 경우 Set안에서도 순서만 바뀐 채 같은 수가 있을 우 있지만, 정렬을 한 뒤이기 때문에 그럴 경우는 없다. 

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> my_set;

        int n = nums.size();
        sort(nums.begin(), nums.end());

        for(int i=0; i<n-2; i++){
            int j = i+1;
            int k = n-1;

            int sum = nums[i];
            while(j < k){
                if((sum + nums[j] + nums[k]) == 0){
                    my_set.insert({nums[i], nums[j], nums[k]});
                    j++;
                    k--;
                }else if((sum + nums[j] + nums[k]) < 0){
                    j++;
                }else{
                    k--;
                }
            }
        }

        vector<vector<int>> ans;

        for(auto nums : my_set){
            ans.push_back(nums);
        }

        return ans;
    }
};

• Time complexity : O(n²) 
• Space Complexity : O(n) 

출처 : 3Sum - LeetCode

3Sum - LeetCode