Three Sum

LeetCode #16

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.

Example:

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

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

Idea:

先排序，然后左右夹逼，Time 复杂度 O(n2)。

这题处理不要重复的情况比较操蛋。

Code:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.size()<3) return vector<vector<int>>{};

        sort(nums.begin(), nums.end());
        vector<vector<int>> result;

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

            if(i>0 && nums[i]==nums[i-1]) continue;

            while(j<k){
                // cout<<i<<' '<<j<<' '<<k<<'\n';
                int three_sum = nums[i]+nums[j]+nums[k];
                if(three_sum==0){
                    result.push_back(vector<int>{nums[i], nums[j], nums[k]});
                    j++;
                    k--;
                    while(nums[j]==nums[j-1]&&nums[k]==nums[k+1] && j<k) {
                        j++;
                        k--;
                    }
                }
                else if(three_sum<0){
                    j++;
                    while(nums[j]==nums[j-1]&& j<k) j++;
                }
                else{
                    k--;
                    while(nums[k]==nums[k+1] && j<k) k--;
                }
            }
        }

        return result;
    }
};

以下的方法也行，但是会超时，不过不用考虑result重复的问题。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.size()<3) return vector<vector<int>>{};

        sort(nums.begin(), nums.end());
        vector<vector<int>> result;

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

            while(j<k){
                int three_sum = nums[i]+nums[j]+nums[k];
                if(three_sum==0){
                    result.push_back(vector<int>{nums[i], nums[j], nums[k]});
                    j++;
                    k--;
                }
                else if(three_sum<0){
                    j++;
                }
                else{
                    k--;
                }
            }
        }

        //Remove duplicated solution:
        sort(result.begin(), result.end());
        result.erase(unique(result.begin(), result.end()), result.end());

        return result;
    }
};