学步园

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)

思路：这道题首先可以想到一种暴力方法，即用三层循环。为了不拥有重复的结果，对数组进行排序。时间复杂度为O(NlogN)。对三层循环进行改进，可以这样，第一层循环的指针为i，表示-a的值，然后指针j和k分别从队首和队尾进行遍历，类似two sum那道题，-a表示target。只需要注意重复的结果，要不然会出现output limited exceeded错误。时间复杂度为O(N^2)。

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > aa;
        vector<int> b;
        aa.clear();
        b.clear();
        int len = num.size();
        sort(num.begin(), num.end());
        int i,j,k;
        for(i=0; i<len; i++)
        {
            while(i>=0 && num[i] == num[i-1])
            {
                ++i;
            }   
            if (num[i] > 0)
            {
                break;
            }     
            for(j=i+1,k=len-1; j<k; )
            {
                if (num[i] + num[j] + num[k] == 0)
                {
                    b.clear();
                    b.push_back(num[i]);
                    b.push_back(num[j]);
                    b.push_back(num[k]);
                    aa.push_back(b);
                    //cout << b[0] << " " << b[1] << " " << b[2] << endl;
                    ++j,--k;
                    while(j<k && (num[j] == num[j-1]) && (num[k] == num[k+1]))
                    {
                        ++j,--k;
                    }    
                    continue;
                }    
                if (num[i] + num[j] + num[k] < 0)
                {
                    ++j;
                    continue;
                }    
                if (num[i] + num[j] + num[k] > 0)
                {
                    --k;
                    continue;
                }    
            }    
        }    
           
        return aa; 
    }
};