发帖
雷达卡
前言
大家好，我是木木。今天我们来攻克 LeetCode 中的一道经典难题——三数之和。
最开始我尝试用三层 for 循环暴力求解，结果不仅超时，还被各种重复的三元组搞得头大。比如 [-1, 0, 1] 和 [0, 1, -1] 其实是同一组数据，但程序却当成两个不同的结果处理。后来学习了高手的做法才明白：想要避免重复，首先要对数组进行排序！一旦排好序，相同的数值就会聚集在一起，去重就变得简单多了。
题目描述
给定一个整数数组 nums，判断是否存在三个不同下标的元素 nums[i]、nums[j]、nums[k]，满足：
- i ≠ j，i ≠ k，j ≠ k
- nums[i] + nums[j] + nums[k] = 0
关键要求是：最终结果中不能包含重复的三元组。
示例：
输入：nums = [-1, 0, 1, 2, -1, -4]
输出：[[-1, -1, 2], [-1, 0, 1]]
注意：虽然原数组中有两个 -1，但结果中不允许出现两组完全相同的组合，如两次 [-1, 0, 1]。
解题策略：排序 + 双指针法
这道题的核心思路是将“找三个数”转化为“固定一个数，再在剩余部分找两个数”，使得三者之和为零。
第一步：数组排序（去重与双指针的基础）
先将数组排序，例如：[-4, -1, -1, 0, 1, 2]。
排序的好处有两点：
- 相同值的元素相邻，便于跳过重复项；
- 利用有序性，可以通过移动左右指针高效查找目标和。
第二步：固定首个元素，双指针寻找另两个
使用变量 i 遍历数组，作为三元组的第一个数 nums[i]。
然后在 i 后面的子数组中设置左指针 L = i + 1 和右指针 R = n - 1，寻找满足以下条件的组合：
nums[i] + nums[L] + nums[R] == 0
第三步：如何有效去重？（核心难点）
去重需要处理三个关键位置：
关卡 A：针对第一个数 nums[i] 的去重
如果当前的 nums[i] 和前一个值相同，说明以它开头的所有可能组合已经在上一轮处理过了，直接跳过即可。
if i > 0 and nums[i] == nums[i-1]: continue关卡 B：针对双指针 L 和 R 找到有效组合后的去重
当找到一组满足条件的三元组后，L 向右移动，R 向左移动。此时若下一个 nums[L] 仍等于当前值，则继续右移，直到遇到不同的数为止，避免产生重复结果。
Python 实现代码
虽然代码稍长，但逻辑清晰，结构分明。
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
# 1. 排序 —— 去重和双指针的前提
nums.sort()
res = []
n = len(nums)
# 2. 遍历第一个数 i
for i in range(n):
# 【剪枝优化】若当前数大于0，则后续所有数相加都不可能等于0
if nums[i] > 0:
return res
# 【去重 A】若当前数与前一个相同，跳过
if i > 0 and nums[i] == nums[i-1]:
continue
# 3. 设置双指针 L 和 R
L = i + 1
R = n - 1
while L < R:
current_sum = nums[i] + nums[L] + nums[R]
if current_sum == 0:
# 找到目标组合，加入结果集
res.append([nums[i], nums[L], nums[R]])
# 【去重 B】L 向右跳过重复值
while L < R and nums[L] == nums[L+1]:
L += 1
# 【去重 C】R 向左跳过重复值
while L < R and nums[R] == nums[R-1]:
R -= 1
# 移动指针进入下一组搜索
L += 1
R -= 1
elif current_sum < 0:
# 和太小，L 右移增大总和
L += 1
else:
# 和太大，R 左移减小总和
R -= 1
return res
在解决三数之和这类问题时，去重是一个关键步骤。为了确保结果中不包含重复的三元组，我们需要在遍历过程中巧妙地跳过相同的元素。
当左指针 L 和右指针 R 找到一组满足条件的解后，需要继续向中间收缩以寻找下一组可能的解。此时，为了避免重复，我们设置“去重关卡 C”：
# 【去重关卡 C】：R 往前找，跳过所有重复的
while L < R and nums[R] == nums[R-1]:
R -= 1
# 找到答案且去重后，两个指针同时收缩
L += 1
R -= 1
[-1, -1, 0, 1]若当前三数之和大于目标值 0，则说明右侧数值过大，需将右指针 R 左移以减小总和：
elif current_sum > 0:
# 和太大了，右边的大个子往回退
R -= 1
nums[0] = -1反之，若当前和小于 0，则说明左侧数值过小，应将左指针 L 右移以增大总和：
else:
# 和太小了，左边的小个子往前走
L += 1
L通过这样的方式，双指针协同移动，逐步逼近所有有效解。
模拟演示去重过程
假设输入数组如下：
-1初始状态：i = 0，固定第一个元素作为基准。
R此时，L 指向 index 1 的位置，即：
1R 指向数组末尾：
-1 + (-1) + 1 = -1 < 0随着指针移动，L 开始右移：
L当找到符合条件的组合时，记录结果：
-1 + 0 + 1 = 0Bingo！成功找到一组解，再次检查并跳过重复值后，继续搜索。最终又发现另一组相同结构的结果：
[-1, 0, 1]接着进入下一轮循环。
i = 1 时的情况：
nums[1] = -1触发“去重关卡 A”：
nums[1] == nums[0]系统判断：以该元素开头的所有组合已在前一轮处理完毕，再次处理会导致重复，因此直接跳过。
i = 2 时继续执行后续流程……
可以看到，只要数组事先排序，去重逻辑就变得非常清晰——只需与前一个元素比较即可判断是否已处理过。所谓去重，本质上就是“跟前一个比一下”这么简单！
-1 + 0 + 1 = 0知识点小课堂
-
为什么必须排序？
如果数组未排序，相同的数值可能会分散在不同位置，例如：
中的两个[-1, 0, 1, -1]
相隔较远，难以判断是否已经组合处理过。而排序之后，相同元素会相邻排列，如：-1
这样就能轻松识别并跳过重复项。nums[i] == nums[i-1] -
为何使用双指针？
使用双指针技巧可以将时间复杂度从暴力枚举的 O(N) 优化至 O(N)。具体来说：- 外层循环固定一个数（i），属于第一层遍历；
- 内层利用 L 和 R 在剩余区间进行双向扫描，仅需一次遍历完成；
iLR
这种基于排序+双指针+去重判断的思路，在多种数组类题目中具有广泛适用性，建议熟练掌握其核心逻辑。
返回最终结果集：
return res
京公网安备 11010802022788号
