三数之和
3Sum
在数组中找出所有和为 0 且不重复的三元组，返回三元组列表。
在力扣中练习题目描述
给你一个整数数组 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
解题思路
主解法
排序 + 双指针
固定第一个数，后两个数用左右指针夹出来
暴力三重循环是 O(n³)，而且还要额外去重。先排序，有两个好处：相同的数相邻，方便跳过重复；数组有序后，后两个数可以用双指针。
固定 nums[i]，令 left = i+1、right = n-1，看三数之和：
- 等于 0：记录答案，跳过 left / right 方向的重复值，再同时收拢；
- 小于 0：需要更大的数，left 右移；
- 大于 0：需要更小的数，right 左移。
自拟主例 [-2,-1,0,1,2,2]：固定 -2 时，0 和 2 配成 [-2,0,2]；固定 -1 时，0 和 1 配成 [-1,0,1]。
分步图解
和 -1 < 0，需要更大的数：left 右移。
- sum
- -1
分步图解
和 1 > 0，需要更小的数：right 左移。
- sum
- 1
时间 O(n²)（排序 O(n log n) 可忽略），空间 O(1)（不计结果和排序栈）。
时间 O(n²)空间 O(1)
易错点
- 忘记跳过重复的 i：同一个三元组会被记录多次。
- 和为 0 后只移动一个指针：会漏掉或重复其他组合；要同时收拢并跳过重复值。
- 在没排序的数组上用双指针：left/right 的移动方向失去依据。
代码与演示
演示输入
nums = [-2,-1,0,1,2,2]先排序；排序后相同的数相邻，才方便跳过重复三元组。
- n
- 6
查看 C++ 代码
延伸阅读
- 三数之和是 k 数之和的基础；四数之和（18）在外层再套一层循环，并做两级去重。
- 如果结果要求按字典序，排序也顺便保证了每个三元组内部有序。