LeetCode 15：三数之和｜排序 + 双指针，如何避免重复答案？

LeetCode 15：三数之和｜排序 + 双指针，如何避免重复答案？

一、题目要求

题目链接：LeetCode 15：三数之和

弄了个网站, 可以看代码是怎么操作达到最终要的结果: 过程可视化

给定一个整数数组nums，找出所有满足以下条件的三元组：

nums[i] + nums[j] + nums[k] = 0

其中i、j、k必须是三个不同的下标，并且答案中不能包含重复的三元组。

例如：

nums=[-1,0,1,2,-1,-4]

输出：

[[-1,-1,2],[-1,0,1]]

注意：题目要求返回的是数字本身，而不是下标。另外，三元组的排列顺序不同，并不代表它们是不同的答案。

二、思路：三个数字，真的需要同时寻找吗？

题目要求三个数字相加等于0。

最直接的办法当然是枚举三个数字，检查它们的和是否为0。

但如果使用三层循环，时间复杂度就会达到 O(n³)。

那么，有没有办法减少一层搜索？

不妨先固定其中一个数字。

假设固定的是：

nums[i]

原本需要满足：

nums[i] + nums[j] + nums[k] = 0

把nums[i]移到右边：

nums[j] + nums[k] = -nums[i]

这样一来，问题就发生了变化。

我们不再需要同时寻找三个数字，而是：

1. 固定第一个数字nums[i]。
2. 计算另外两个数字需要凑出的和need = -nums[i]。
3. 在剩余数组中寻找两个数字，使它们相加等于need。

也就是说，三数之和可以拆成：固定一个数字 + 寻找另外两个数字。

接下来需要考虑的是：剩下两个数字怎么找，才能避免再次使用两层循环？

三、排序 + 双指针：寻找剩下两个数字

如果剩下两个数字也用两层循环枚举，那么整体仍然是 O(n³)。

但如果数组有序，我们就可以根据两个数字的总和，判断应该移动哪一边。

因此，先对数组排序：

nums.sort()

例如：

原数组：[-1, 0, 1, 2, -1, -4] 排序后：[-4, -1, -1, 0, 1, 2]

现在先固定一个数字nums[i]，再让两个指针分别指向它右边的第一个数字和数组末尾：

j=i+1k=n-1

其中：

• i：固定第一个数字。
• j：左指针，寻找第二个数字。
• k：右指针，寻找第三个数字。

为什么从i + 1开始？

因为nums[i]已经被固定，我们只需要在它后面寻找另外两个数字，既不会重复使用同一个下标，也不需要重新考虑前面的组合。

1. 当前总和太小

假设：

nums = [-4, -1, -1, 0, 1, 2] ↑ ↑ ↑ i j k

固定：

nums[i] = -4 need = 4

另外两个数字需要相加等于4。

但现在：

nums[j] + nums[k] = -1 + 2 = 1

发现1 < 4。

因为数组已经排序，2是当前搜索范围中最大的数字，连-1 + 2都不够，那么-1和范围内其他数字相加也不可能达到4。

所以可以排除当前左端数字，让左指针向右移动：

j+=1

2. 当前总和太大

反过来，如果：

nums[j] + nums[k] > need

说明另外两个数字的和太大。

因为nums[j]已经是当前范围内最小的数字，连它与nums[k]相加都超过目标，那么nums[k]与范围内其他数字相加只会更大或相等。

因此可以排除右端数字：

k-=1

3. 当前总和刚好等于 need

如果：

nums[j] + nums[k] == need

说明：

nums[i] + nums[j] + nums[k] == 0

找到一个满足条件的三元组：

result.append([nums[i],nums[j],nums[k]])

但这里还不能直接结束。

因为题目要求找出所有不同的三元组，而不是找到一个就返回。

因此，记录答案以后，还要继续移动左右指针，寻找其他可能的组合。

到这里，基本的搜索规则就确定了：

固定 nums[i] ↓ need = -nums[i] ↓ 在 i 后面使用左右双指针 ↓ 总和太小 → j += 1 总和太大 → k -= 1 总和相等 → 记录答案，继续寻找

不过，这道题与普通两数之和还有一个很大的区别：重复答案。

四、为什么需要去重？

例如：

nums=[-2,0,0,2,2]

我们可能多次找到：

-2 + 0 + 2 = 0

但正确答案只能是：

[[-2,0,2]]

因为即使使用的是不同下标，只要三个数字相同，就属于重复的三元组。

所以，除了找到答案，还需要考虑如何避免重复。

这里主要有两个位置需要去重。

1. 固定数字 nums[i] 的去重

例如：

nums = [-2, -2, 0, 2, 2] ↑ i

如果第一个-2已经处理完，那么当i移动到第二个-2时，就没有必要重新搜索一遍。

因为固定的数字相同，后面可能找到的三元组也会重复。

因此：

ifi>0andnums[i]==nums[i-1]:continue

意思是：如果当前固定的数字与上一个相同，就跳过这次搜索。

这里要特别注意：

不能只要看到重复数字就全部跳过。

例如：

nums=[-1,-1,2]

正确答案就是：

[[-1,-1,2]]

我们允许三元组内部出现相同的数字，只是不允许结果列表中出现重复的三元组。

因此，固定数字的去重只针对不同轮次的i，不能因此禁止另外两个指针使用相同数值。

2. 找到答案后，左右指针也需要去重

例如：

nums = [-2, 0, 0, 2, 2] ↑ ↑ ↑ i j k

找到：

-2 + 0 + 2 = 0

之后，先记录答案：

result.append([nums[i],nums[j],nums[k]])

然后移动左右指针：

j+=1k-=1

但新位置上的数字可能与刚刚使用过的数字相同。

所以还需要跳过这些重复值：

whilej<kandnums[j]==nums[j-1]:j+=1whilej<kandnums[k]==nums[k+1]:k-=1

为什么分别比较j - 1和k + 1？

因为我们已经先执行了：

j+=1k-=1

所以：

• j - 1是左指针刚刚经过的位置。
• k + 1是右指针刚刚经过的位置。

如果新位置的数字与刚才一样，就继续跳过，直到遇到不同的数字，或者两个指针相遇。

这样就能避免同一个固定数字下，重复记录相同的三元组。

五、完整解法：排序 + 固定一个数字 + 双指针 + 去重

现在把前面的思路组合起来：

classSolution:defthreeSum(self,nums:list[int])->list[list[int]]:result=[]nums.sort()n=len(nums)foriinrange(n-2):# 固定数字去重ifi>0andnums[i]==nums[i-1]:continueneed=-nums[i]j=i+1k=n-1whilej<k:current=nums[j]+nums[k]ifcurrent<need:j+=1elifcurrent>need:k-=1else:result.append([nums[i],nums[j],nums[k]])j+=1k-=1# 跳过左侧重复数字whilej<kandnums[j]==nums[j-1]:j+=1# 跳过右侧重复数字whilej<kandnums[k]==nums[k+1]:k-=1returnresult

到这里，已经能够正确解决这道题。

容易踩的坑

① 找到答案后，指针必须继续移动。

如果只是把答案添加到result，但没有改变j和k，下一轮仍然会检查同一组数字。

这会导致循环无法结束，结果列表不断增长，甚至出现内存超限。

② 返回的是数字，不是下标。

应该记录：

[nums[i],nums[j],nums[k]]

而不是：

[i,j,k]

③ 去重不等于禁止使用相同的数字。

例如[-1, -1, 2]是合法答案。

我们要排除的是重复三元组，而不是所有重复元素。

④ 固定数字只需要遍历到 n - 3。

代码中使用：

foriinrange(n-2):

因为固定一个数字以后，右边至少还需要两个元素。

如果数组长度小于 3，循环自然不会执行，最终返回空列表。

六、进一步优化：利用排序进行剪枝

前面的解法已经能够通过题目，时间复杂度也达到了 O(n²)。

不过既然数组已经排序，我们还能不能利用它的大小关系，提前排除一些根本不可能得到答案的情况？

例如，每次固定nums[i]后，我们都会让左右指针搜索一遍。

但有些时候，甚至不需要进入双指针循环，就已经能够判断当前数字不可能组成答案。

这就是剪枝。

优化 1：最大的两个数字都不够，跳过当前 i

例如：

nums = [-20, -10, -5, 1, 2, 3] ↑ i

固定：

nums[i] = -20

即使选择后面最大的两个数字：

-20 + 2 + 3 = -15

仍然小于0。

这说明固定-20时，无论另外两个数字怎么选，都不可能得到答案。

因此可以直接跳过当前i：

ifnums[i]+nums[n-2]+nums[n-1]<0:continue

这里使用continue，因为当前固定数字太小，不代表后面更大的固定数字也不行。

优化 2：最小的两个数字都超了，直接结束

反过来，如果固定当前数字以后，选择右边最小的两个数字，总和都已经大于0呢？

例如：

nums = [-5, -2, 4, 6, 8, 10] ↑ i

固定4，选择右边最小的两个数字：

4 + 6 + 8 = 18

已经大于0。

既然这是当前固定数字能够得到的最小总和，那么其他组合只会更大。

而且数组已经排序，后面的固定数字也只会更大，因此后续同样不可能找到答案。

所以：

ifnums[i]+nums[i+1]+nums[i+2]>0:break

这里使用break，直接结束外层循环。

两种剪枝的区别

简单理解：

• 太小了：换下一个固定数字试试。
• 太大了：后面只会更大，可以直接结束。

七、最终优化版代码

在基本解法的基础上，加入两个剪枝条件：

classSolution:defthreeSum(self,nums:list[int])->list[list[int]]:result=[]nums.sort()n=len(nums)foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:continue# 最大的两个数字都不够ifnums[i]+nums[n-2]+nums[n-1]<0:continue# 最小的两个数字都超了ifnums[i]+nums[i+1]+nums[i+2]>0:breakneed=-nums[i]j=i+1k=n-1whilej<k:current=nums[j]+nums[k]ifcurrent<need:j+=1elifcurrent>need:k-=1else:result.append([nums[i],nums[j],nums[k]])j+=1k-=1whilej<kandnums[j]==nums[j-1]:j+=1whilej<kandnums[k]==nums[k+1]:k-=1returnresult

剪枝不会改变最坏时间复杂度，但可以减少一些不必要的搜索。

需要注意的是，这两个剪枝是进一步优化，并不是双指针算法能够成立的必要条件。

八、复杂度分析

时间复杂度：O(n²)

首先对数组排序：

nums.sort()

排序的时间复杂度为 O(n log n)。

然后通过外层循环固定第一个数字：

foriinrange(n-2):

最多需要 O(n) 次。

每次固定一个数字后，左右指针从两端向中间移动，总移动次数最多为 O(n)。

因此双指针搜索部分的时间复杂度为：

O(n) × O(n) = O(n²)

最终由 O(n²) 主导。

额外空间复杂度：

双指针搜索本身只使用固定数量的变量，为 O(1)。

但 Python 的排序可能需要额外空间，返回的结果列表也需要占用内存，因此整个实现的实际空间开销不能简单地全部算成 O(1)。

九、总结

这道题最关键的思路，是把寻找三个数字的问题拆开：

先固定一个数字，再寻找另外两个数字。

这样就不需要用三层循环枚举所有组合。

然后利用数组有序的特点，通过左右双指针寻找剩下两个数字，把搜索的时间复杂度从 O(n³) 降到 O(n²)。

不过，三数之和还有一个不能忽略的问题：去重。

题目允许不同位置上的数字相同，但不允许答案中出现重复的三元组。因此需要分别处理固定数字的重复，以及找到答案后左右指针遇到的重复数字。

至于最后的剪枝，只是在基本解法正确的基础上，进一步利用排序后的大小关系减少无效搜索。

如果想继续理解「为什么左右双指针可以安全地排除某一端的数字」，也可以参考我之前整理的 LeetCode 167：两数之和 II｜双指针思路解析。

两道题的共同点是利用有序性缩小搜索范围，而这道题额外需要解决的，就是固定一个数字后如何寻找所有不重复的组合。