15. 三数之和（力扣LeetCode）

文章目录

15. 三数之和
- 题目描述
- 双指针
- - 去重逻辑的思考
  - - a的去重
    - b与c的去重
- 哈希表

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⁵ <= nums[i] <= 10⁵

双指针

其实这道题目使用哈希法并不十分合适，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有bug的代码。

而且使用哈希法在使用两层for循环的时候，能做的剪枝操作很有限，虽然时间复杂度是O(n^2)，也是可以在leetcode上通过，但是程序的执行时间依然比较长。

接下来我来介绍另一个解法：双指针法，这道题目使用双指针法要比哈希法高效一些，那么来讲解一下具体实现的思路。

动画效果如下：

在这里插入图片描述

拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。

接下来如何移动left 和right呢，如果nums[i] + nums[left] + nums[right] > 0 就说明此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明此时三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

时间复杂度：O(n^2)。

class Solution {
public:
    // 主函数，调用此函数来找到所有不重复的三数之和为零的组合
    vector<vector> threeSum(vector& nums) {
        // 注释掉的快速排序，留作参考或者选择排序方法
        // quick_sort(nums, 0, nums.size() - 1); // 快速排序

        // 使用归并排序对数组进行排序
        merge_sort(nums, 0, nums.size() - 1);

        // 定义用于存放结果的二维向量
        vector<vector> result;
		
		// 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        // 遍历排序后的数组，寻找三数之和为零的组合
        for (int i = 0; i < nums.size(); i++) {
            // 如果当前数字大于0，则后续不可能找到三数之和为零的组合（因为数组已排序）
            if (nums[i] > 0) break;
			
			// 错误去重a方法，将会漏掉-1,-1,2 这种情况
            /*
            if (nums[i] == nums[i + 1]) {
                continue;
            }
            */

            // 去重：跳过连续相同的数字，以避免重复的三元组
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            // 定义左指针和右指针
            int l = i + 1, r = nums.size() - 1;
            // 当左指针小于右指针时，执行循环
            while (l < r) {
            	// 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                */
                
                // 计算三数之和
                int sum = nums[i] + nums[l] + nums[r];
                // 根据三数之和与零的比较，移动指针
                if (sum > 0) r--; // 和大于零，移动右指针以减小和
                else if (sum < 0) l++; // 和小于零，移动左指针以增大和
                else {
                    // 找到有效的三元组，加入结果集
                    result.push_back({nums[i], nums[l], nums[r]});
                    // 去重：跳过左侧连续相同的数字
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    // 去重：跳过右侧连续相同的数字
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    // 移动左右指针准备寻找下一个可能的组合
                    l++, r--;
                }
            }
        }

        // 返回最终的结果集
        return result;
    }

private:
    // 快速排序函数，已注释掉，但可供选择使用
    void quick_sort(vector& n, int l, int r) {
        if (l >= r) return;

        // 快速排序的分区操作
        int i = l - 1, j = r + 1, x = n[l + r >> 1];
        while (i < j) {
            do i++; while (n[i]  x);
            if (i < j) swap(n[i], n[j]);
        }

        // 递归排序左半部
        quick_sort(n, l, j);
        // 递归排序右半部
        quick_sort(n, j + 1, r);
    }

    // 用于归并排序的临时数组
    int tmp[3000];

    // 归并排序函数
    void merge_sort(vector& n, int l, int r) {
        if (l >= r) return; // 如果区间只有一个元素或为空，则不进行操作

        // 计算中点，用于分割数组
        int mid = l + r >> 1;
        // 递归排序左半部分
        merge_sort(n, l, mid);
        // 递归排序右半部分
        merge_sort(n, mid + 1, r);

        // 归并操作：合并两个有序数组
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            // 选取两个数组中较小的一个加入到临时数组中
            if (n[i] < n[j]) tmp[k++] = n[i++];
            else tmp[k++] = n[j++];
        }

        // 将剩余元素加入临时数组
        while (i <= mid) tmp[k++] = n[i++];
        while (j <= r) tmp[k++] = n[j++];

        // 将临时数组中的元素复制回原数组
        for (int i = l, j = 0; i <= r; i++, j++) n[i] = tmp[j];
    }
};

去重逻辑的思考

a的去重

说到去重，其实主要考虑三个数的去重。 a, b ,c, 对应的就是 nums[i]，nums[left]，nums[right]

a 如果重复了怎么办，a是nums里遍历的元素，那么应该直接跳过去。

但这里有一个问题，是判断 nums[i] 与 nums[i + 1]是否相同，还是判断 nums[i] 与 nums[i-1] 是否相同。

有同学可能想，这不都一样吗。

其实不一样！

都是和 nums[i]进行比较，是比较它的前一个，还是比较它的后一个。

如果我们的写法是这样：

if (nums[i] == nums[i + 1]) { // 去重操作
    continue;
}

那我们就把三元组中出现重复元素的情况直接pass掉了。例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断下一个也是-1，那这组数据就pass了。

我们要做的是不能有重复的三元组，但三元组内的元素是可以重复的！

所以这里是有两个重复的维度。

那么应该这么写：

if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}

这么写就是当前使用 nums[i]，我们判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到结果集里。

这是一个非常细节的思考过程。

总结：去重的原则是：有了才能重，还没有就不会重(没法预测未来, 但要保证走过的路不要再走)

b与c的去重

很多同学写本题的时候，去重的逻辑多加了对right 和left 的去重：（代码中注释部分）

while (right > left) {
    if (nums[i] + nums[left] + nums[right] > 0) {
        right--;
        // 去重 right
        while (left < right && nums[right] == nums[right + 1]) right--;
    } else if (nums[i] + nums[left] + nums[right] < 0) {
        left++;
        // 去重 left
        while (left < right && nums[left] == nums[left - 1]) left++;
    } else {
    }
}

但细想一下，这种去重其实对提升程序运行效率是没有帮助的。

拿right去重为例，即使不加这个去重逻辑，依然根据 while (right > left) 和 if (nums[i] + nums[left] + nums[right] > 0) 去完成right– 的操作。

多加了 while (left < right && nums[right] == nums[right + 1]) right–; 这一行代码，其实就是把需要执行的逻辑提前执行了，但并没有减少判断的逻辑。

最直白的思考过程，就是right还是一个数一个数的减下去的，所以在哪里减的都是一样的。

所以这种去重是可以不加的。仅仅是把去重的逻辑提前了而已。

哈希表

这段代码的思路是，先遍历a（i=0开始），然后新定义一个unordered_set set;（用来存储b），再遍历b（从i+1开始），c=0-(a+b)，如果在set中没找到c，则当前的 b 就成了一个潜在的候选，它可能会与后续的其他元素配对成功构成三元组。因此，我们将这个 b 添加到 set 中，以便后续的元素可以检查它是否可以成为它们的配对元素 c。

如果在集合中没有找到满足条件的 c，那意味着对于当前的 a 和 b，不存在一个已经遍历过的数能和它们组合成三元组。然而，我们不能就此忽视了 b，因为它可能和之后的某个数 c 组合，和 a 一起形成一个新的有效三元组。

举个例子，假设我们有一个已排序的数组 nums = [-4, -1, -1, 0, 1, 2]，我们要找不重复的三元组，其和为 0。

我们首先固定 a = -4（i = 0），然后开始内层循环寻找 b 和 c。
我们将 b 设置为 -1（j = 1），这时我们需要找到一个数 c = – a – b = 4 + 1 = 5。由于 5 不在数组中，我们将 -1（当前的 b）添加到集合中。
我们将 b 更新为第二个 -1（j = 2），我们再次需要找一个数 c = 5，因为集合中还没有，我们不用更新集合。
接下来我们将 b 设置为 0（j = 3），这时我们需要找到一个数 c = 4。我们查看集合，发现没有 4，所以我们将 0 添加到集合中。
我们将 b 设置为 1（j = 4），这时我们需要的 c = 3。集合中没有 3，我们将 1 添加到集合中。
最后我们将 b 设置为 2（j = 5），我们需要的 c = 2。现在我们检查集合，发现集合中包含 2，所以我们找到了一个解：[-4, 2, 2]。

在这个例子中，即使我们在集合中没有找到匹配的 c，我们仍然需要将 b 添加到集合中，因为在后续迭代中，我们仍然可能会找到与 a 和这个 b 匹配的 c。这个例子演示了如何通过逐步添加元素到集合中来寻找潜在的三元组。

然而，这个例子中的解 [-4, 2, 2] 并不是有效的，因为我们需要三个不同的数。但这个过程说明了当内层循环没有找到匹配的 c 时，如何将 b 添加到集合中以备后续查找的逻辑。实际代码中还应当包括进一步的逻辑来确保找到的三个数都是不同的，并且没有重复的三元组。

所以对b的去重也应当改变：

原本对b的去重应为：

if (j > i + 1 && nums[j] == nums[j-1]) {
    continue; // 跳过相同的 b
}

现在应该变为：

 if (j > i + 2&& nums[j] == nums[j-1]&& nums[j-1] == nums[j-2]) 
 {
         continue;
 }

以[-2,0,1,1,2]举例：

当a=-2时，b从0开始枚举：

当b=0时，c=0-(-2+0)=2，set中不存在2，将0存入set
当b=1时，c=0-(-2+1)=1，set中不存在1，将1存入set
当b=1时，此时j > i + 2&& nums[j] == nums[j-1]&& nums[j-1] == nums[j-2]，1==1，但1！=0，不跳过，因为1存在与set中，所以这是一个不重复的三元组，如果是j > i + 1 && nums[j] == nums[j-1]这个条件的话，就被跳过了，就得不到[-2,1,1]元组了
当b=2时，c=0-(-2+2)=0，set中存在0，这是一个新的三元组[-2,2,0]

该方法是用了先将b存入set中，如果后面的c符合a+b+c=0的条件，那么一定能够在set中找到c的思想，所以对b的去重就需要是j > i + 2&& nums[j] == nums[j-1]&& nums[j-1] == nums[j-2]，例如输入[0,0,0],这样去重才能得到正确答案。

总结：这里和双指针解法的去重逻辑是不太一样的。对于 j 来说，它往后遍历，将碰到的数加入到 set 集合中，之后继续往后遍历，寻找 c 的时候是在集合中找，也就是说在 j 的前面的元素中找。这个逻辑和前面的去重 b 是相关的，正因为要记录遍历到的数到 set 中，才需要设定 j > i+2 的条件，因为 i，i+1，i+2 正好是三个数，这三个数有可能是结果，而出现更多相同的就一定是重复结果了

class Solution {
public:
    // 函数threeSum接收一个整数类型的vector，返回一个二维vector，包含所有不同的三元组
    vector<vector> threeSum(vector& nums) {
        vector<vector> result; // 用来存储最终结果的二维向量
        sort(nums.begin(), nums.end()); // 首先对nums进行排序，这样便于去重和后续处理

        // 开始遍历数组
        for (int i = 0; i < nums.size(); i++) {
            // 已排序，如果当前数字大于0，则后面不可能有三个数加和等于0
            if (nums[i] > 0) {
                break;
            }
            // 去重：如果当前数字与前一个数字相同，则跳过此次循环
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 哈希集合用于存储遍历过程中的数字，以及验证某个数是否为需要的目标数
            unordered_set set;
            // 从当前数字的下一个开始遍历
            for (int j = i + 1; j < nums.size(); j++) {
                // 进一步去重：确保j的指示的元素不是连续重复的元素
                if (j > i + 2
                        && nums[j] == nums[j-1]
                        && nums[j-1] == nums[j-2]) {
                    continue;
                }
                int c = 0 - (nums[i] + nums[j]); // 计算第三个数字
                // 如果集合中已存在第三个数字，则找到了一个解，并将其添加到结果中
                if (set.find(c) != set.end()) {
                    result.push_back({nums[i], nums[j], c}); // 将找到的三元组添加到结果集
                    set.erase(c); // 为了避免重复的三元组，从集合中删除第三个数字
                } else {
                    // 如果第三个数字不在集合中，将当前数字添加到集合中以供后续查找
                    set.insert(nums[j]);
                }
            }
        }
        return result; // 返回最终的三元组结果集
    }
};

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://www.net2asp.com/c369b19874.html