题目链接：https://leetcode.cn/problems/3sum/

1.排序+双指针

思路如下：

对数组进行排序。枚举第一个数 n u m s [ i ] nums[i] nums[i]，跳过第一个数的重复数字。双指针寻找第二个数 n u m s [ l ] nums[l] nums[l] 和第三个数 n u m s [ r ] nums[r] nums[r]。

令左指针 l = i + 1 l=i+1 l=i+1，右指针 r = n − 1 r=n−1 r=n−1，当 l < r l<r l<r 时，执行循环：

• 若三数之和小于 0 0 0，说明 n u m s [ l ] nums[l] nums[l] 太小， l l l 右移；
• 若三数之和大于 0 0 0，说明 n u m s [ r ] nums[r] nums[r] 太大， r r r 左移；
• 若三数之和等于 0 0 0，则保存当前解 { n u m s [ i ] , n u m s [ l ] , n u m s [ r ] } \left\{ nums[i], nums[l], nums[r] \right\} {nums[i],nums[l],nums[r]}，并将 l , r l, r l,r 移到下一位置，寻找新的解。同时判断新位置的数是否和上一位置的数重复，跳过第二个数和第三个数的重复数字。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        sort(nums.begin(), nums.end()); // 对数组进行排序
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过第一个数的重复数字
            int l = i + 1, r = n - 1;
            while (l < r) {
                int t = nums[i] + nums[l] + nums[r];
                if (t < 0) {
                    l++;
                } else if (t > 0) {
                    r--;
                } else {
                    res.push_back({nums[i], nums[l], nums[r]});
                    l++;
                    r--;
                    while (l < r && nums[l] == nums[l - 1]) l++; // 跳过第二个数的重复数字
                    while (l < r && nums[r] == nums[r + 1]) r--; // 跳过第三个数的重复数字
                }
            }
        }
        return res;
    }
};

2.对上面代码加剪枝

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        sort(nums.begin(), nums.end()); // 对数组进行排序
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过第一个数的重复数字
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break; // 剪枝一
            if (nums[i] + nums[n - 2] + nums[n - 1] < 0) continue; // 剪枝二
            int l = i + 1, r = n - 1;
            while (l < r) {
                int t = nums[i] + nums[l] + nums[r];
                if (t < 0) {
                    l++;
                } else if (t > 0) {
                    r--;
                } else {
                    res.push_back({nums[i], nums[l], nums[r]});
                    l++;
                    r--;
                    while (l < r && nums[l] == nums[l - 1]) l++; // 跳过第二个数的重复数字
                    while (l < r && nums[r] == nums[r + 1]) r--; // 跳过第三个数的重复数字
                }
            }
        }
        return res;
    }
};