Python算法训练序列

双指针与滑动窗口 · Unit 04

← Unit 03
15
LeetCode 153Sum · 三数之和

固定一个数，
把三数问题降维成两数问题。

排序以后，枚举锚点 i，再在右侧区间寻找和为 -nums[i] 的两个数。真正的难点不是求和，而是确保相同数值组合只进入答案一次。

LeetCode #15 原题内容中文转述 · 示例、约束与提交签名

题目要求

给定整数数组 nums，返回所有互不重复的三元组 [nums[i], nums[j], nums[k]]，满足三个下标彼此不同，且三个数之和为 0。答案中不能包含重复三元组，输出顺序不限。

class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: # 返回所有不重复的和为0的三元组

约束

  • 3 ≤ len(nums) ≤ 3000
  • -100000 ≤ nums[i] ≤ 100000

示例

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

核心约束

不同下标允许拥有相同数值，但答案按“数值三元组”去重，而不是按下标组合去重。

1. 识别三重枚举
2. 固定锚点降维
3. 建立三层去重
4. 代码联动
5. 最接近迁移
排序后：[-4,-1,-1,0,1,2]等待操作
锚点 nums[i]-4
左值 nums[left]-1
右值 nums[right]2
three_sum-3
已经收集的不重复三元组
result = []

当前循环不变量

锚点固定后，若存在尚未找到的答案，它一定仍位于 [left,right] 中。

当前去重规则

重复锚点不重新处理；命中答案后，跳过与当前left和right相同的连续值。

anchor i0
left / right1 / 5
当前和-3
已跳过重复0
结果数量0
三重枚举的瓶颈

三个下标分别枚举时，候选数量达到 O(n³)。即使使用集合对答案去重，仍没有减少组合搜索成本，也没有解释如何稳定地产生唯一三元组。

补全 LeetCode 提交代码重点：移动与去重
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result = []
for i in range(len(nums) - 2):
if nums[i] > 0:
break
if :
continue
left, right =
while left < right:
three_sum =
if three_sum < 0:
left += 1
elif three_sum > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
while left < right and :
left += 1
while left < right and :
right -= 1
left += 1
right -= 1
return result
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() result = [] for i in range(len(nums) - 2): if nums[i] > 0: break if i > 0 and nums[i] == nums[i - 1]: continue left, right = i + 1, len(nums) - 1 while left < right: three_sum = nums[i] + nums[left] + nums[right] if three_sum < 0: left += 1 elif three_sum > 0: right -= 1 else: result.append([nums[i], nums[left], nums[right]]) while left < right and nums[left] == nums[left + 1]: left += 1 while left < right and nums[right] == nums[right - 1]: right -= 1 left += 1 right -= 1 return result
三层去重不要混为一谈：锚点去重防止同一个第一元素重新生成整批结果；命中后的left/right去重防止固定锚点下重复生成同一个三元组。排序让重复值相邻，因此可以通过连续比较完成去重。
代码—锚点—双指针—去重联动轨迹：[-4,-1,-1,0,1,2]
1class Solution:
2 def threeSum(self, nums: List[int]) -> List[List[int]]:
3 nums.sort()
4 result = []
5 for i in range(len(nums) - 2):
6 if nums[i] > 0:
8 if i > 0 and nums[i] == nums[i - 1]:
11 left, right = i + 1, len(nums) - 1
12 while left < right:
13 three_sum = nums[i] + nums[left] + nums[right]
15 if three_sum < 0: left += 1
17 elif three_sum > 0: right -= 1
20 result.append([nums[i], nums[left], nums[right]])
22 while ... nums[left] == nums[left + 1]: left += 1
24 while ... nums[right] == nums[right - 1]: right -= 1
27 left += 1; right -= 1
29 return result
逐行播放，观察固定锚点后如何找到两组答案并跳过重复锚点。
完成代码联动后进入最接近三数之和迁移补全正确、查看答案或播放完整轨迹后解锁。

迁移题：LeetCode #16 最接近的三数之和

仍然先排序、固定锚点并使用左右指针。区别在于不再只关心是否等于目标，而要持续维护与 target 距离最小的 best_sum。

本单元形成的算法Skill

面对三数和问题，先排序并固定一个锚点，把问题降维成右侧区间的两数之和。外层控制锚点，内层双指针利用单调性移动；锚点、left和right分别承担不同层级的去重责任。

LeetCode #15排序降维固定锚点相向双指针三层去重O(n²)
#125镜像比较
#283读写指针
#167单调排除
#15 当前锚点＋双指针＋去重
#3 下一单元滑动窗口与重复字符