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]]

核心约束

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

先连接上一单元：把“两数单调排除”嵌入一个外层锚点Unit 03 → Unit 04
#167：一个有序区间

left 与 right 在整个数组上收缩，目标是找到唯一一组两数之和。

→
#15：多个有序子区间

每固定一个 anchor，就在它右侧重新建立一组 left/right，把三数问题降成两数问题。

新增的不是另一套双指针，而是一层外部控制：anchor 决定当前两数目标，left/right 仍沿用 Unit 03 的单调移动；去重则负责避免同一数值组合被不同路径重复生成。
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 最接近的三数之和

先完整理解迁移题要解决什么、返回什么，再讨论它与 #15 的联系。完成原题阅读检查后，才进入“排序＋锚点＋相向双指针”的结构迁移。

1. 认识 #16 原题
2. 对照枚举与最优化
3. 映射四个语义变化
4. 拼装并运行最优状态

先读题：最接近的三数之和

这一阶段只确认任务目标、输入输出和约束，不提前套用 #15 的算法。

LeetCode #16 · Medium
题目要求

给定长度至少为 3 的整数数组 nums 和整数 target，从数组中选择三个不同下标的元素，使三个数之和与 target 最接近，并返回这个三数之和。

class Solution: def threeSumClosest(self, nums: List[int], target: int) -> int: # 返回最接近 target 的三数之和
约束与保证
  • 3 ≤ len(nums) ≤ 500
  • -1000 ≤ nums[i] ≤ 1000
  • -10000 ≤ target ≤ 10000
  • 题目保证最接近的结果唯一。
原题示例
输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：-1 + 2 + 1 = 2，与目标1的距离为1。
输入：nums = [0,0,0], target = 1 输出：0 解释：唯一三元组的和为0。
选择三个不同下标 最小化绝对距离 返回“和” 不是返回三元组

读题检查 A｜函数最终应该返回什么？

读题检查 B｜示例 [-1,2,1,-4], target=1 为什么返回2？

先完成两道读题检查。理解“返回最接近的和，而不是返回三元组”后，才进入算法结构对照。

已经掌握：#15 三数之和

搜索结构：排序 → 固定 anchor → left/right 目标：收集所有 current_sum == 0 的三元组 结果状态：result 列表 命中后：append、两侧去重、继续搜索 重复路径：必须通过锚点与两侧去重消除

准备迁移：#16 最接近的三数之和

搜索结构：排序 → 固定 anchor → left/right 目标：让 |current_sum - target| 尽量小 结果状态：一个 best_sum 每一轮：先比较距离，再按大小移动指针 重复路径：不会产生重复输出，去重不再是正确性要求
保持不变排序、外层锚点、右侧区间、三数求和，以及“偏小移动 left、偏大移动 right”的单调方向。
需要替换删除 result 列表与三层去重；新增 best_sum，并在每次指针移动前比较当前距离是否更优。
从“可行解枚举”跨到“最优化搜索” #15 的循环不变量关注“尚未遗漏哪些精确答案”；#16 新增的状态不变量是：best_sum 始终是已经检查过的三元组中，与 target 距离最小的和。只有先更新这个状态，才能安全移动指针。

先判断迁移幅度：下面哪句话最准确？

槽位 A｜best_sum 为什么不能随便初始化为0或target？

槽位 B｜每轮计算 current_sum 后，怎样维护“目前最接近”？

槽位 C｜指针移动要围绕哪个参照值？

槽位 D｜若精确命中以及遍历结束，分别返回什么？

为什么精确命中可以立即返回？距离的理论下界是0。一旦 current_sum == target，已经不可能出现更接近的结果。
复用的搜索骨架nums.sort()、外层 anchor、left=i+1、right=n-1 与单调收缩全部保留。
删除的枚举机制不再维护 result，不再 append 三元组；锚点和两侧去重也不再是输出正确性的必要条件。
新增的状态不变量每轮移动前，best_sum 已吸收当前三元组，因此它始终代表已扫描部分中的最优答案。

#15：枚举所有精确三元组

nums.sort()
result = []
for i in range(len(nums)-2):
    跳过重复 anchor
    left, right = i+1, len(nums)-1
    while left < right:
        current_sum = ...
        if current_sum < 0: left += 1
        elif current_sum > 0: right -= 1
        else:
            result.append(...)
            跳过重复 left/right
return result

#16：维护一个最接近的和

nums.sort()
best_sum = nums[0]+nums[1]+nums[2]
for i in range(len(nums)-2):
    left, right = i+1, len(nums)-1
    while left < right:
        current_sum = ...
        若距离更小，更新 best_sum
        if current_sum < target: left += 1
        elif current_sum > target: right -= 1
        else:
            return target
return best_sum
迁移运行轨迹0/0
可选挑战：脱离槽位，独立重写完整代码

这一步不阻碍主流程。编辑器已经保留排序、锚点和双指针骨架，你只需要补回“更新最优状态”和移动分支。

本单元形成的算法Skill

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

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