描述

在一个有n个元素的数组S中，是否存在三个数字a，b，c是的a+b+c = 0？找到所有的不同的这样的三组数字的组合。

要求：

• 找到的三个数字要按照升序排列：a<=b<=c；
• 不能包含重复解；

分析

先把数组排序，然后设定三个游标，第一个游标index1指向数组的第一个元素，第二个游标index2指向第二个元素，第三个游标index3指向数组的最后一个元素，设定A[index1]+A[index2]+A[index3] = result，则result的取值有以下三种情况：

• result == 0，找到一组解，则++index2, --index3；
• result > 0，需要减小等式中的数字，--index3，index2保持不变；
• result < 0，需要加大等式中的数字，++index2，index3保持不变；

对于index1的查找的结束条件是：*index2>=index3。

代码实现如下：

vector<vector<int>> threeSum(vector<int> &num)
{
    vector<vector<int>> result;
    if (num.size() < 3) {
        return result;
    }
    sort(num.begin(), num.end());
    const int target = 0;
    auto last = num.end();
    for(auto a=num.begin(); a<prev(last, 2); ++a) {
        auto b = next(a);
        auto c = prev(last);
        
        while (b < c) {
            if (*a + *b + *c < target) {
                ++b;
            } else if (*a + *b + *c > target) {
                --c;
            } else {
                result.push_back({*a, *b, *c});
                ++b;
                --c;
            }
        }
    }
    sort(result.begin(), result.end());
    result.erase(unique(result.begin(), result.end()), result.end());
    return result;
}

代码在这儿