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

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;
}