【九】【算法分析与设计】双指针（3）

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000

-10(5) <= nums[i] <= 10(5)

暴力枚举：

为了避免出现重复的元素，我们对nums数组进行排序，然后把相同的元素不计算，直接跳过。

题目的要求是不包含重复的三元组，所以我没每一次后移i，j，k的时候不可以简单的后移，而是往后移动到下一个不重复的数字上，这样就不会重复计算相同的元素。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        int n = nums.size();
        for (int i = 0; i < n;) {
            for (int j = i + 1; j < n;) {
                for (int k = j + 1; k < n;) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        ret.push_back({nums[i], nums[j], nums[k]});
                    }
                    k++;
                    while (k < n && nums[k] == nums[k - 1])
                        k++;
                }
                j++;
                while (j < n && nums[j] == nums[j - 1])
                    j++;
            }
            i++;
            while (i < n && nums[i] == nums[i - 1])
                i++;
        }
        return ret;
    }
};

双指针优化暴力枚举：

首先对nums排序。

固定三元组中最大的一个数，记为nums[i]，那么问题就转化为找两数之和为target=-nums[i]的组合。令left=0，right=i-1，我们需要遍历的是[left,right]区间内，每两两组合。

sum=nums[left]+nums[right]，如果sum>target，那么对于right与left+1,left+2.....right-1这些数的组合一定也大于target，因为nums是有序的，下标和值分别看作x与y函数，函数就是递增的。所以nums[left+1],nums[left+2].....一定大于nums[left]，所以right与后面的组合都可以不用再考虑，一定也不符合题意。这样对于right的组合情况就全部考虑完毕了。此时对right--,相同的数再次right--，直到数不相同，防止重复计算。

如果sum<target，那么对于left与right-1,right-2....left+1这些数的组合一定也小于target，因为nums是有序的，下标和值分别看作x与y函数，函数就是递增的。所以nums[right-1],nums[right-2].....一定小于nums[right]，所以left与后面的组合都可以不用再考虑，一定也不符合题意。这样对于left的组合情况就全部考虑完毕了。此时对left++，相同的数再次left++，直到数不相同，防止重复计算。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        int n = nums.size();
        for (int i = n - 1; i >= 2;) {
            int left = 0, right = i - 1;
            int target = -nums[i];
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum > target) {
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    ret.push_back({nums[left++], nums[right--], nums[i]});

                    while (left < right && nums[left] == nums[left - 1])
                        left++;
                    while (left < right && nums[right] == nums[right + 1])
                        right--;
                }
            }

            i--;
            while (i >= 2 && nums[i] == nums[i + 1])
                i--;
        }

        return ret;
    }
};

class Solution {public: vector<vector<int>> threeSum(vector<int>& nums) {

定义了一个名为 threeSum 的成员函数，它接受一个名为 nums 的整数向量的引用作为参数，并返回一个二维向量，其中包含所有满足条件的三元组。

sort(nums.begin(), nums.end());

首先对输入的向量 nums 进行排序，这是为了后续能够使用双指针技术来避免重复的三元组并简化搜索过程。

vector<vector<int>> ret;

定义了一个名为 ret 的二维向量，用于存储最终的结果。

int n = nums.size();for (int i = n - 1; i >= 2;) {

获取 nums 的大小赋值给 n，并从数组的末尾开始遍历，因为我们要找三个数的组合，所以至少需要3个数。

int left = 0, right = i - 1;int target = -nums[i];

初始化两个指针 left 和 right，分别指向当前子数组的开始和 i 之前的位置。target 是我们要找的两数之和，它是 nums[i] 的相反数。

while (left < right) {int sum = nums[left] + nums[right];

在 left 指针小于 right 指针的情况下，计算 left 和 right 指向的两个数的和。

if (sum > target) { right--;} else if (sum < target) { left++;} else { ret.push_back({nums[left++], nums[right--], nums[i]});

如果 sum 大于 target，需要减小 sum，所以 right 指针左移，可以理解为与right组合的所有情况考虑完毕；如果 sum 小于 target，需要增大 sum，所以 left 指针右移，可以理解为与left组合的所有情况考虑完毕；如果 sum 等于 target，说明找到了一个有效的三元组，将其添加到结果 ret 中，并移动两个指针寻找下一个可能的三元组。

while (left < right && nums[left] == nums[left - 1]) left++;while (left < right && nums[right] == nums[right + 1]) right--;

这两个循环用来跳过相同的元素，避免重复的三元组。

i--;while (i >= 2 && nums[i] == nums[i + 1]) i--;

递减 i 并跳过相同的元素，以便在下一轮循环中处理不同的 nums[i]。

时间复杂度和空间复杂度分析

时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。外层循环最多执行 n 次，内层循环（双指针）在每次外层循环中最多执行 n 次。

空间复杂度：O(1) 或 O(n)，这取决于排序算法的实现，如果排序算法是原地排序，则空间复杂度为 O(1)，否则为 O(n)。

18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n

a、b、c 和 d 互不相同

nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]

提示：

1 <= nums.length <= 200

-10(9) <= nums[i] <= 10(9)

-10(9) <= target <= 10(9)

暴力枚举：

为了避免重复计算，我们先把nums数组进行排序，然后跳过计算相同的元素。对于i，j，k，l每一次不是简单的往后移一位，而是往后移到下一个不重复的元素位置。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> ret;
        sort(nums.begin(),nums.end());
        for (int i = 0; i < n;) {
            for (int j = i + 1; j < n;) {
                for (int k = j + 1; k < n;) {
                    for (int l = k + 1; l < n;) {
                        if ((long long)nums[i] + nums[j] + nums[k] + nums[l] == target)
                            ret.push_back({nums[i], nums[j], nums[k], nums[l]});

                        l++;
                        while (l < n && nums[l] == nums[l - 1])
                            l++;
                    }
                    k++;
                    while (k < n && nums[k] == nums[k - 1])
                        k++;
                }
                j++;
                while (j < n && nums[j] == nums[j - 1])
                    j++;
            }
            i++;
            while (i < n && nums[i] == nums[i - 1])
                i++;
        }

        return ret;
    }
};

双指针优化暴力枚举：

首先固定一位数，问题转化为求三数和，再固定一位，问题转化为求两数和，求两数和用双指针，对撞指针进行暴力枚举的优化，快速找到符合条件的情况。

需要注意的是数据的计算过程又可以超出界限，所以aim我们不用int而用longlong，后面的计算表达式只需要把一个强转为longlong即可。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());

        for (int i = 0; i < n;) {
            for (int j = i + 1; j < n;) {
                int left = j + 1, right = n - 1;
                long long aim = (long long)target - nums[i] - nums[j];

                while (left < right) {
                    int sum = nums[left] + nums[right];
                    if (sum < aim)
                        left++;
                    else if (sum > aim)
                        right--;
                    else {
                        ret.push_back(
                            {nums[i], nums[j], nums[left], nums[right]});
                        right--;
                        left++;
                        while (left < right && nums[left] == nums[left - 1])
                            left++;
                        while (left < right && nums[right] == nums[right + 1])
                            right--;
                    }
                }
                j++;
                while (j < n && nums[j] == nums[j - 1])
                    j++;
            }
            i++;
            while (i < n && nums[i] == nums[i - 1])
                i++;
        }
        return ret;
    }
};

class Solution {public: vector<vector<int>> fourSum(vector<int>& nums, int target) {

定义了一个名为 fourSum 的成员函数，它接受一个整数数组 nums 和一个目标值 target 作为参数，并返回一个二维向量，其中包含所有满足条件的四元组。

int n = nums.size(); vector<vector<int>> ret;sort(nums.begin(), nums.end());

获取 nums 的大小并赋值给 n，定义一个用于存储结果的二维向量 ret，并对 nums 进行排序，排序就作用是便于我们进行去重操作。

for (int i = 0; i < n;) {

使用外层循环遍历 nums，i 是四元组中第一个数字的位置。

for (int j = i + 1; j < n;) {

使用内层循环遍历 nums，j 是四元组中第二个数字的位置。

int left = j + 1, right = n - 1;long long aim = (long long)target - nums[i] - nums[j];

初始化双指针 left 和 right，分别指向四元组中第三和第四个数字的起始位置。计算剩余两数的目标和 aim。

while (left < right) {int sum = nums[left] + nums[right];

在 left 小于 right 的情况下，计算 left 和 right 指针指向的两个数的和。