1. 三数之和

题目链接

基本原理大家应该都比较熟悉，使用双指针消去一层循环，将时间复杂度降低一个量级，如O(n3)降低到O(n2)，O(n4)降低到O(n3)。但是其中的很多剪枝操作还是值得注意的，这些剪枝操作可以有效降低代码的实际运行时间（因为它们避免了很多无效遍历）。先看代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), i, j, k, target;
        vector<vector<int>> ans;
        for (i = 0; i < n - 2; ++i) {
            // 这里用if去重是因为后面要用到i，如果while不好处理
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            if (nums[i] > 0) break;
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
            if (nums[i] + nums[n - 2] + nums[n - 1] < 0) continue;
            target = -nums[i];
            j = i + 1; k = n - 1;
            while (j < k) {
                // if (nums[i] + nums[j] > 0) break;
                if (nums[j] + nums[k] < target) ++j;
                else if (nums[j] + nums[k] > target) --k;
                else {
                    ans.push_back({nums[i], nums[j], nums[k]});
                    // 这里用while去重是因为后面不用j和k了
                    while (j < k && nums[j] == nums[j + 1]) ++j;
                    while (j < k && nums[k] == nums[k - 1]) --k;
                    ++j; --k;
                }
            }
        }
        return ans;
    }
};

另外就是每个指针的去重操作，以三数之和为例，这里的三个指针i, j和k都需要去重，主要原因都是避免重复计算，但是去重的方法不太一样，比如下面这里i的去重：

// 这里用if去重是因为后面要用到i，如果while不好处理
if (i > 0 && nums[i] == nums[i - 1]) continue;

而j和k的去重：

// 这里用while去重是因为后面不用j和k了
while (j < k && nums[j] == nums[j + 1]) ++j;
while (j < k && nums[k] == nums[k - 1]) --k;
++j; --k;

这里因为i是在外层for循环中（每次循环结束自动++），而且后面要用到i的值，因此如果直接在这里用while去重会不好处理，因此只用if在每轮for里面处理一次。而对于j和k的去重，这里是在找到正确答案以后去重，因为答案组合不能是重复的。但为什么两侧指针都需要去重呢（和最接近的三数之和不同）？主要是因为只移动单侧指针都不可能得到正确答案：只右移左指针，三数和变大，大于目标和；只移动右指针，三数和变小，小于目标和；因此还不如左右一起移。而没找到正确答案时，也不用去重，反正下一次即使是重复还是找不到正确答案。（当然也可以去重，不过代码太啰嗦）

再看剪枝部分，对于外层i的剪枝，有两种，粗剪和细剪，粗剪：

if (nums[i] > 0) break;

不必多说，只要三数中最左的都>0，那么也就不用接着往下找了。而细剪：

if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
if (nums[i] + nums[n - 2] + nums[n - 1] < 0) continue;

可能不太直观，但是仔细看便可发现端倪。第一句的意思是，如果目前最小的三个数，其和大于0，那么不用找了，后面也找不到了，break；而第二句的意思是，如果目前可能的最大的三个数和都小于0，那当前循环肯定是找不到了，应该让i变大再来找，因此continue;
最后是一个可选剪枝：

if (nums[i] + nums[j] > 0) break;

这句的意思是，如果第一个数和第二个数之和已经>0了，也没必要再继续了，因为此时前两个数中至少有一个>0的数（否则它们的和一定≤0），那么第三个数一定是>0的，三个数的和也一定是>0的，因此break；不过这句用处不大。

2. 最接近的三数之和

题目链接

先贴代码：

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int i, j, k, n = nums.size(), res, diff = INT_MAX, temp;
        for (i = 0; i < n - 2; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            temp = nums[i] + nums[i + 1] + nums[i + 2];
            if (temp > target) {
                if (temp - target < diff) {
                    diff = temp - target;
                    res = temp;
                }
                break;
            }
            temp = nums[i] + nums[n - 2] + nums[n - 1];
            if (temp < target) {
                if (target - temp < diff) {
                    diff = target - temp;
                    res = temp;
                }
                continue;
            }
            j = i + 1; k = n - 1;
            while (j < k) {
                temp = nums[i] + nums[j] + nums[k];
                if (temp == target) return temp;
                else if (temp < target) {
                    if (target - temp < diff) {
                        diff = target - temp;
                        res = temp;
                    }
                    while (j < k && nums[j] == nums[j + 1]) ++j;
                    ++j;
                } else {
                    if (temp - target < diff) {
                        diff = temp - target;
                        res = temp;
                    }
                    while (j < k && nums[k] == nums[k - 1]) --k;
                    --k;
                }
            }
        }
        return res;
    }
};

其实和上一题基本的框架类似，不过细节上有差异：比如i不再需要粗剪枝，因为这里找的是离目标最近的三数和。但是去重和细剪枝还是需要的，去重很好理解，避免重复计算，但是细剪枝呢？

temp = nums[i] + nums[i + 1] + nums[i + 2];
if (temp > target) {
    if (temp - target < diff) {
    	diff = temp - target;
        res = temp;
    }
    break;
}

如上，如果当前可能最小的三个数其和已经大于target，i往后走已经没有意义（往后走和target只会越来越远），因此取本次的三数和来更新答案，之后break掉。对于当前可能最大的三个数其和小于target的情况也是和三数之和类似，i需要更大，来使得三数和离target更近。
对于j和k的去重，这里是在当前三数和≠target数进行，毕竟等于的话直接就返回了。而且不能像上一题一样j和k同时往中间移动去重，会导致一些答案被忽略。（上一题我们可以同时往中间移动是因为我们找到了正确答案，但在这里，我们并不知道有没有找到正确答案）因此对于三数和<target的情况，我们希望让和更大（从而距离更小），那么将j右移去重；反正则将k左移去重。

temp = nums[i] + nums[j] + nums[k];
if (temp == target) return temp;
else if (temp < target) {
    if (target - temp < diff) {
        diff = target - temp;
        res = temp;
    }
    while (j < k && nums[j] == nums[j + 1]) ++j;
    ++j;
} else {
    if (temp - target < diff) {
        diff = temp - target;
        res = temp;
    }
    while (j < k && nums[k] == nums[k - 1]) --k;
    --k;
}

3. 四数之和

题目链接

本题基本和三数之和一致，但是外层for循环由一层增加到两层，并且目标和也由0变成了任意target，但是基本思想不变，外层循环粗剪-去重-细剪三部曲，找到正确答案后两个指针向中间靠拢去重。这里的粗剪有所变化，之前目标和为0时，我们直接根据nums[i] > 0即可剪枝，但是，一旦target为任意值，我们就不能单纯的通过nums[i] > target来剪枝，因为target可能为负值，比如target为-8，当前nums[i]为-4，可能i后面还有-4，此时无法剪枝。还需要增加一个判断条件，就是nums[i] ≥ 0。

if (nums[i] > target && nums[i] >= 0) break;

这个条件说明后面三个数j, k和l一定是非负数，因此四数之和无论如何也会比target大，i往后再走没有意义，此时才能break剪枝。而对于第二层循环中j的粗剪枝，也类似：

if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) break;

nums[i] + nums[j] >= 0说明i和j中至少一个非负数（否则其和为负数），那么k和l明显也是非负数，而nums[i] + nums[j] > target这，将导致四数和总是大于target，因此可以剪枝。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int i, j, k, l, n = nums.size();
        long temp;
        vector<vector<int>> ans;
        if (n < 4) return ans;
        sort(nums.begin(), nums.end());
        for (i = 0; i < n - 3; ++i) {
            // 粗剪
            if (nums[i] > target && nums[i] >= 0) break;
            // 去重
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            // 细剪
            if ((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            if ((long)nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;
            for (j = i + 1; j < n - 2; ++j) {
                if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) break;
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                if ((long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
                if ((long)nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue;
                k = j + 1; l = n - 1;
                while (k < l) {
                    temp = (long)nums[i] + nums[j] + nums[k] + nums[l];
                    if (temp < target) ++k;
                    else if (temp > target) --l;
                    else {
                        ans.push_back({nums[i], nums[j], nums[k], nums[l]});
                        while (k < l && nums[k] == nums[k + 1]) ++k;
                        while (k < l && nums[l] == nums[l - 1]) --l;
                        ++k; --l;
                    }
                }
            }
        }
        return ans;
    }
};