3Sum问题(a+b+c=0?)

本题来自LeetCode中Problems 3sum。

问题描述：

输入：数组S={a1,a2,...,an},其中ai为任意整数，n为数组中元素数目

输出：序列对（a,b,c）组成的数组，使得a+b+c=0，其中a≤b≤c，且（a,b,c）序列不重复

eg:

输入：S={-1,0,1,2,-1,-4}

输出：(-1,0,1)、(-1,-1,2)

思路：1、由于要求a≤b≤c,由此可考虑先对整个数组按非递减排序，对于非递减的数组，可以从其两端依次扫描符合条件的序列对（a,b,c）；2、设置三个指针，假设这三个指针p1,p2,p3指向的值分别为a,b,c，为满足a+b+c=0，则可固定住p1不变，p2，p3分别从数组的前(除第一个元素)端和后端开始扫描，若a+b+c>0，因数组是非递减的，肯定是因为此时c较大，此时应该--p2,若a+b+c<0,则是因为b较小，此时++p1，若a+b+c=0，则将其保存。

算法复杂度：O(n*n)

vector<vector<int> > threeSum(vector<int> &num) {    // Note: The Solution object is instantiated only once and is reused by each test case.    vector<vector<int>> vecRlt;    if (num.size() < 3)    {        return vecRlt;    }    sort(num.begin(),num.end());    vector<int> vecTriple(3);    int iFirst = 0;    int iSecond = 0;    int iThird = num.size() - 1;    for (;iFirst < num.size() - 2 && num[iFirst] <= 0; ++iFirst)    {           iSecond = iFirst + 1;        iThird = num.size() - 1;        if (iFirst > 0 && num[iFirst] == num[iFirst-1])        {            continue;        }        while (iSecond < iThird)        {            int iSum = num[iFirst] + num[iSecond];            if (iSum + num[iThird] > 0)            {                --iThird;            }            else if (iSum + num[iThird] < 0)            {                ++iSecond;            }            else            {                vecTriple[0] = num[iFirst];                vecTriple[1] = num[iSecond];                vecTriple[2] = num[iThird];                vecRlt.push_back(vecTriple);                ++iSecond;                --iThird;                //消除后面重复的数                while(iSecond<iThird && num[iSecond] == num[iSecond-1])                {                    ++iSecond;                }                //消除前面重复的数                while(iSecond<iThird && num[iThird] == num[iThird+1])                {                    --iThird;                }            }        }    }    return vecRlt;}