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

> 发布于：2022-03-13 | 分类：刷题 | 原文：https://www.imbailey.cn/post/leetcode-15-3sum-two-pointers

## 题目

#### [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）那么有没有不需去重的办法呢？

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

```c++
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不用回溯。
* 我写不下去了...其实我理解的很烂



那直接上我的代码吧：

```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;
        }
};
```

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



**2025年 2 月 23 日更新**

这段代码是双指针标准模板，更好理解

```Python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        for i in range(len(nums)-2):
            if i==0 or nums[i]!=nums[i-1]:
                left = i+1
                right = len(nums)-1
                target = 0-nums[i]
                # 双指针
                while left < right:
                    if nums[left] + nums[right] == target:
                        res.append([nums[i], nums[left], nums[right]])
                        left += 1
                        right -= 1
                        # 跳过重复
                        while left<right and nums[left]==nums[left-1]:
                            left += 1
                        while left<right and nums[right]==nums[right+1]:
                            right -= 1
                    else:
                      	# 这里无需跳过重复，因为不满足nums[left] + nums[right] == target的过程不会记录
                        if nums[left]+nums[right] > target:
                            right -= 1
                        else:
                            left += 1
        return res
                        

```