Leetcode: 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},

A solution set is:

(-1, 0, 1)

(-1, -1, 2)

递归：

void threeSumHelper(vector<int> &num, int index, vector<int> &path, int cursum, vector<vector<int>> &res)  
    {  
        if(path.size() >=3)  
        {  
            if(path.size() == 3 && cursum == 0)  
            {  
                res.push_back(path);  
                return;  
            }else  
                return;  
        }  
        for(int i = index; i < num.size(); i++)  
        {  
            path.push_back(num[i]);  
            cursum += num[i];  
            threeSumHelper(num,i+1,path,cursum,res);  
            path.pop_back();  
            cursum -= num[i];  
            while(i < num.size()-1 && num[i] == num[i+1])i++;  
        }  
    }  
    vector<vector<int> > threeSum(vector<int> &num) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        vector<vector<int>> res;  
        if(num.size()<3)return res;  
        sort(num.begin(), num.end());  
        vector<int> path;  
        threeSumHelper(num,0,path,0,res);  
        return res;  
    }

2sum变形:

vector<vector<int> > threeSum(vector<int> &num) {          // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        vector<vector<int>> res;  
        if(num.size()<3)return res;  
  
        set<vector<int>> tmpres;  
        sort(num.begin(), num.end());  
          
        for(int i = 0; i < num.size(); i++)  
        {  
            int target = - num[i];  
            int begin = i+ 1;  
            int end = num.size()-1;  
            while(begin < end)  
            {  
                int sum = num[begin] + num[end];  
                if( sum == target)  
                {  
                    vector<int> tmp;  
                    tmp.push_back(num[i]);  
                    tmp.push_back(num[begin]);  
                    tmp.push_back(num[end]);  
                    tmpres.insert(tmp);  
                    begin++;  
                    end--;  
                }else if(sum < target)  
                    begin++;  
                else  
                    end--;  
            }  
        }  
        set<vector<int>>::iterator it = tmpres.begin();  
        for(; it != tmpres.end(); it++)  
            res.push_back(*it);  
        return res;  
    }

补充：软件开发 , C++ ,