开始前应具备
- 完成复杂度与哈希章节
- 理解数组下标和原地修改
- 能描述闭区间与半开区间
CHAPTER 02 · 线性技巧
用快慢、左右指针压缩枚举范围,把很多平方级搜索降到线性级。
BEFORE LEARNING
双指针的本质是维护一段已经满足定义的区间,并利用顺序或单调性跳过不可能的组合。它是数组、链表和滑动窗口的共同基础。
开始前应具备
完成本章后
CORE LESSONS
LESSON
要求在原数组上删除、去重或移动元素,并限制额外空间时使用。
快指针扫描所有输入,慢指针指向下一个有效写入位置。慢指针之前始终是已经整理好的答案区,因此无需真的删除数组元素。
slow = 0
for fast in range(n):
if should_keep(a[fast]):
a[slow] = a[fast]
slow += 1LESSON
数组有序,或区间两端的选择能确定哪一侧不可能成为更优答案时使用。
左右指针不是盲目夹逼。每次移动都必须排除一整组不可能解。以盛水问题为例,容量受短板限制,因此移动长板不会改善当前短板造成的上限。
left, right = 0, n - 1
while left < right:
update_answer(left, right)
if move_left_condition: left += 1
else: right -= 1LESSON
要求寻找多个元素的目标和,同时答案不能重复时,考虑排序后固定一个元素再双指针。
排序让和值随指针移动呈单调变化,也让重复值相邻。三数之和由此降为“枚举第一个数 + 两数之和”,并能在同一层跳过重复答案。
sort(a)
for i in range(n):
if duplicate_i: continue
left, right = i + 1, n - 1
while left < right: compare_sum()READING
先读完本站讲义并尝试练习;遇到推导不清的地方,再回到原始教程深入阅读。
PRACTICE LADDER
题量由知识点决定,不再固定为 5 道。先完成“入门”和“模板”,再做变式与综合;挑战题可以留到复习阶段。
3 道 · 依次完成
Remove Element
为什么选:最直接的原地写入练习。
Remove Duplicates
为什么选:训练慢指针所代表的有效区间。
Move Zeroes
为什么选:把删除转化为稳定移动并补零。
3 道 · 依次完成
Two Sum II
为什么选:有序数组中根据和值决定移动方向。
Container With Most Water
为什么选:需要证明为什么移动短板。
Trapping Rain Water
为什么选:通过左右最大值建立更复杂的不变量。
1 道 · 依次完成
3Sum
为什么选:集中训练排序、固定元素、双指针和去重。
PERSONAL NOTEBOOK
笔记保存在当前浏览器