力扣题目解析--三数之和

题目

给你一个整数数组 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
• -105 <= nums[i] <= 105

代码展示 

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end()); // 对数组进行排序

        for (int i = 0; i < nums.size() - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复元素

            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++; // 和太小，增加左边的数
                } else if (sum > 0) {
                    right--; // 和太大，减少右边的数
                } else {
                    // 找到一个解
                    result.push_back({nums[i], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) left++; // 跳过重复的左指针
                    while (left < right && nums[right] == nums[right - 1]) right--; // 跳过重复的右指针
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
};

写者心得 

对于这一道题目，我刚开始的想法就是用一个循环，再加上一个超长的if循环解决这个问题。可是刚一开始调试if循环的条件就报了错。在学习请教的过程中，我觉得这个代码有着以下的几个亮点：

1.在设定动态数组的时候，使用二维数组。（我刚开始接触这个题目的时候，我所设定的数组并没有考虑到二维数组。而题目要求的那个结果却是二维数组，没有认出来，这是我学识上的不足。）

2.代码的第二步就对数组进行了排序（一步的目的其实是为了之后使用双指针做铺垫，,但是在我刚开始对于题目思考的时候，也根本没有考虑到先将元素进行排序之后，更容易得到数组前后两个数的和是否为0）

3.如果在if循环中条件过多，就应该考虑使用while循环。（他说了我刚开始就是给if循环里面加了一大堆条件，事实证明这样的路是走不通的。如果以后遇到了多条件的题目的时候，就应该考虑使用while循环，而不是在if循环里不断套用。）

4.双指针，它的精髓在于在数组中找三个数和为零的数字（我在之前的编程中其实使用过双指针，但是那时候我看的不太懂。现在我可以总结出双指针使用的情况，应该就在于与前后两个数有关系的时候，双指针能发挥很大的作用。）

5.跳过重复元素。（这一步看似平平无奇，但其实是使用双指针至关重要的前提，试想一下，如果遇到重复的元素，其输出的结果会对于我们对于整个代码的逻辑产生非常严重的影响。而且，这样的困扰会一直伴随着我们对于代码的读写和思考）

6.去重（这一点是我根本就没有想到的，或者说我的思路还没有到这一步，但是代码用了两个while循环，轻松解决了在得到目标数组之后，如果在二维数组中这个数组与其他的数组重复的时候的问题。）

 

代码解释 

定义和初始化

vector<vector<int>> result;

这行代码创建了一个空的二维向量 result。每个内部的 vector<int> 将会保存一个三元组。

添加元素

当你找到一个满足条件的三元组时，你可以将其添加到 result 中：

result.push_back({nums[i], nums[left], nums[right]});

这里的 {nums[i], nums[left], nums[right]} 是一个初始化列表，它会被转换成一个 vector<int> 并添加到 result 的末尾。

sort(nums.begin(), nums.end()); // 对数组进行排序

使用 sort 函数对输入数组 nums 进行升序排序。排序后，可以通过双指针法有效地查找满足条件的三元组。

for (int i = 0; i < nums.size() - 2; i++) {

开始一个外层循环，遍历数组中的每一个元素，作为第一个数 nums[i]。这里 i 的范围是从 0 到 nums.size() - 3，因为还需要两个额外的位置来放置另外两个数。

if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复元素

如果当前元素 nums[i] 与前一个元素相同，则跳过本次循环，避免产生重复的三元组。

int left = i + 1, right = nums.size() - 1;

初始化两个指针 left 和 right，分别指向当前元素 nums[i] 后的第一个位置和数组的最后一个位置。

while (left < right) {

进入一个内层循环，当 left 指针小于 right 指针时继续循环。

int sum = nums[i] + nums[left] + nums[right];

计算当前三个指针所指向的元素之和 sum。

if (sum < 0) {
    left++; // 和太小，增加左边的数

如果 sum 小于零，说明当前和太小，需要增大 left 指针所指向的数，因此将 left 向右移动一位。

} else if (sum > 0) {
    right--; // 和太大，减少右边的数

如果 sum 大于零，说明当前和太大，需要减小 right 指针所指向的数，因此将 right 向左移动一位。

} else {
    // 找到一个解
    result.push_back({nums[i], nums[left], nums[right]});

如果 sum 等于零，说明找到了一个满足条件的三元组，将其添加到结果列表 result 中。

while (left < right && nums[left] == nums[left + 1]) left++; // 跳过重复的左指针

为了避免产生重复的三元组，如果 left 指针所指向的数与下一个数相同，则继续将 left 向右移动。

while (left < right && nums[right] == nums[right - 1]) right--; // 跳过重复的右指针

同理，如果 right 指针所指向的数与前一个数相同，则继续将 right 向左移动。

left++;
right--;

无论是否有重复的数，都需要将 left 和 right 指针各向中间移动一位，以便继续查找新的可能的三元组。

return result;

返回结果列表 result，其中包含了所有满足条件的三元组。

 

原文地址：https://blog.csdn.net/wxtg1921/article/details/143524529

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！