三数之和——双指针——好难

2022-03-13 约 888 字预计阅读 2 分钟次阅读

题目

[15. 三数之和]

难度中等4464收藏分享切换为英文接收动态反馈

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 *a，b，c ，*使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

示例 1：

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

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

题解

参考官方题解

思路可以很快确定，难点在于精确调控指针。所以我调了三个小时的代码才通过…可能我单纯就是菜qwq

首先我们想到用三个循环暴力把这些三元组找出来，然后再对结果去重。（话说c++对二维向量去重我也不会呀qwq）那么有没有不需去重的办法呢？

当然有了，且看如下伪代码：

nums.sort() // 对nums排序,使得三元组(a,b,c)满足a<=b<=c
for first = 0 .. n-1
    // 只有和上一次枚举的元素不相同，我们才会进行枚举
    if first == 0 or nums[first] != nums[first-1] then
        for second = first+1 .. n-1
            if second == first+1 or nums[second] != nums[second-1] then
                for third = second+1 .. n-1
                    if third == second+1 or nums[third] != nums[third-1] then
                        // 判断是否有 a+b+c==0
                        check(first, second, third)

这样保证了两点：

第二重循环枚举到的元素不小于当前第一重循环枚举到的元素，且不与上一个枚举到的元素重复。
第三重循环枚举到的元素不小于当前第二重循环枚举到的元素，且不与上一个枚举到的元素重复。

不懂的话可以看看官方题解，再找一个数组，比如[-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6]在纸上画一画。

双指针

假设三元组为(a,b,c)。当a确定时，这里的双指针就是b和c，双指针用到了如下性质：

在三重枚举的过程中，当a确定时，b增大，c减小。c不用回溯。
我写不下去了…其实我理解的很烂

那直接上我的代码吧：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end()); // 排序
        int n = nums.size();
        vector<vector<int>> res;
        int first,second,third; // 定义三个“指针”
        for(first=0;first<n;first++){
            if(first==0 || nums[first]!=nums[first-1]){ // 这里有个巧妙的地方，
              // 先判断first==0，如果成立，不用继续判断，数组不会越界
                third = n-1; // 当first+1时，才回溯third
                for(second=first+1;second<n;second++){
                    if(second==first+1 || nums[second]!=nums[second-1]){
                        while(second<third && nums[first]+nums[second]+nums[third]>0){
                            third = third-1;
                        }
                        if (second == third) {// 指针不能重合
                            break;
                        }
                        if(nums[first]+nums[second]+nums[third]==0){
                            res.push_back({nums[first],nums[second],nums[third]});
                        }
                    }
                    
                }

            }
        }
        return res;
        }
};

感觉这个过程还蛮复杂的，可能过一段时间再看会清晰一点。

目录

三数之和——双指针——好难

题目

[15. 三数之和]

题解