3Sum

给定一个数组，如果存在三个数的和为0，求这三个数a、b、c，并使得a<=b<=c， 不得有重复出现

思路：和2SUM一样，先排序，然后取出一个数，作为2SUM的target，进行查找。
注意点：不得有重复，需要每次得到一个结果以后进行首尾去重

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> >res;
        if (num.size() <3)
        {
            return res;
        }
        sort(num.begin(), num.end());
        int target = 0, head = 0, tail = 0;
        for (size_t i = 0; i < num.size()-1; i++)
        {
            if (i > 0 && num[i - 1] == num[i])
                continue;
            target = num[i] * (-1);
            for (head=i+1,tail = num.size()-1; head < tail;)
            {
                if (num[head]+num[tail] > target)
                {
                    tail--; continue;
                }
                if (num[head] + num[tail] < target)
                {
                    head++; continue;
                }
                if (num[head] + num[tail] == target)
                {
                    vector<int> subRes;
                    subRes.push_back(num[i]);
                    subRes.push_back(num[head]);
                    subRes.push_back(num[tail]);
                    res.push_back(subRes);
                    while (head<tail && num[head] == num[head + 1])
                    {
                        head++;
                    }
                    while (head<tail && num[tail] == num[tail - 1])
                    {
                        tail--;
                    }
                    head++;
                }
            }
        }
        return res;
    }
};

3Sum

原文：http://www.cnblogs.com/flyjameschen/p/4378347.html