3Sum 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: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets. For example, given array S = {-1 0 1 2 -1 -4}, …

threeSum.cc

class Solution {
public:
    // based on two sum
    void twoSum(vector<int> & num, vector<vector<int> > & res, int target)
    {
        int n = num.size();
        int i = 0, j = n-1;
        int prei = INT_MAX;// note ensure uniqueness
        int prej = INT_MAX;
        while(i<j)
        {
            prei = num[i];
            prej = num[j];
            int sum = num[i] + num[j];
            if(sum == target)
            {
                vector<int> t;
                t.push_back(num[i]);
                t.push_back(num[j]);
                res.push_back(t);
                ++i; --j; // gurantee uniqueness
                while(i<n && num[i] == prei) // when equal, skip the same value
                    ++i;
                while(j>=0 && num[j] == prej) // when equal, skip the same value
                    --j;
            }else if(sum < target)
                ++i;
            else
                --j;
        }
    }
    
    vector<vector<int> > threeSum(vector<int> &num) {
        int n = num.size();
        vector<vector<int> > res;
        if(n<3)
            return res;
        sort(num.begin(), num.end());
        int preNum = INT_MAX;
        for(int i = n-1; i>=2; --i)
        {
            if(num[i] == preNum) // do not choose the already selected number
                continue;
            preNum = num[i];
            int target = 0-num[i];
            int preSize = res.size();
            vector<int> tNum(num.begin(), num.begin()+i);
            twoSum(tNum, res, target);
            for(int j = preSize; j<res.size(); ++j)
            {
                res[j].push_back(num[i]);
            }
        }
        return res;
    }
};