描述 Description

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: 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] ]

[3Sum]

分析 Analysis

相比2SUM多了几个难点：

1. 数组里允许重复的数

2. 结果要按升序排列

3. 结果中不能出现重复的结果

方法：夹逼方法(k-sum通用方法)

先排序，然后左右夹逼，先固定一个数left（最外层循环遍历），另两个数在left右边排好序的数组上遍历，小数在左边为mid，大数在右边为right，如果两数和>k-left，则必然是右边数太大，所以right左移，否则是左边数太小，所以mid右移}。

首先，我们考虑如何确定第一个数left，这肯定是我们第一层循环。但是第一个数不能无限制的随便选，因为我们要保证上面的几个条件都满足，我们要保证它时刻是最小的数，那么我们可以考虑left取到全部非正数就行了（也可以设定mid比left大）。（如果要和为0，至少要有1个非正数）

    for (int left = 0; left < nums.length && nums[left] <= 0; left++)

然后就是mid和right的确定了，我们采用思路2的方案，mid和right分别从两端往中央扫描，如果mid+right还比较小，那就需要mid右移，反之right左移。

虽然这个能解决问题2，但是不能处理重复结果。举个最简单的例子： -2 -2 -1 -1 0 1 1 2 2 这个代码会输出数个[-2 0 2] [-1 0 1] ，解决方案也很简单，如果一个left指向的数是之前判断过的跳过，如果mid和right往中间移动的时候是刚才的数也跳过。

时间复杂度O(n2)。

这个方法可以推广到k-sum，先排序，然后做k-2次循环，在最内层循环左右夹逼，时间复杂度是O(max{nlogn,n^(k−1)})。

代码 Code

vector<vector<int> > threeSum(vector<int> &num) {
    vector<vector<int> > res;
    std::sort(num.begin(), num.end());

    for (int i = 0; i < num.size(); i++) {
        int target = -num[i];
        int front = i + 1;
        int back = num.size() - 1;

        while (front < back) {
            int sum = num[front] + num[back];

            // Finding answer which start from number num[i]
            if (sum < target)
                front++;
            else if (sum > target)
                back--;
            else {
                vector<int> triplet(3, 0);
                triplet[0] = num[i];
                triplet[1] = num[front];
                triplet[2] = num[back];
                res.push_back(triplet);

                // Processing duplicates of Number 2
                while (front < back && num[front] == triplet[1]) front++;

                // Processing duplicates of Number 3
                while (front < back && num[back] == triplet[2]) rear--;
            }

        }
        // Processing duplicates of Number 1
        while (i + 1 < num.size() && num[i + 1] == num[i]) 
            i++;

    }
    return res;
}