双指针：从移动规则
到正确性证明
13 道 LeetCode · Python 3 完整答案 · 5 个学习阶段
把“两个下标怎么动”，学成“为什么这样动不会漏解”。
每题的学习闭环：理解接口 → 定义指针 → 建立不变量 → 解释移动规则 → 推演边界 → 独立默写。先学能证明的思路，再追求代码熟练度。
题意为针对学习目标的转述，每题保留官方原题链接；解法、证明、图解及学习安排为本手册编写。阅读、复制、演示和进度保存无需网络，原题链接需联网。
学习路线：先区间，再证明
| 阶段 | 题目顺序 | 完成标准 |
|---|---|---|
| 1 · 相向指针入门 | 344 → 125 | 定义未处理区间，明确相遇时为什么停止。 |
| 2 · 双序列协作 | 1768 → 392 → 88 | 覆盖任一输入先结束，并解释从后写的原因。 |
| 3 · 同向读写与稳定划分 | 27 → 26 → 283 | 区分有效长度、物理长度与保序要求。 |
| 4 · 候选排除与有序搜索 | 11 → 15 | 证明短板移动与有序和的移动方向。 |
| 5 · 进阶边界与匹配 | 75 → 42 → 28 | 解释未知区、可结算位置与失配回退。 |
第 28 题虽然标为简单，但 KMP 需要单独理解前缀复用，因此放在最后。先完成朴素匹配，再进入进阶解法。阶段仅表示学习顺序，不改变原题难度。
基础知识：指针其实是边界
在 Python 数组与字符串题中，“指针”通常只是整数下标。两个位置相互协作：每次推进都确定一部分答案、消费一段输入，或排除一批不可能更优的候选。
| 类型 | 含义与推进规则 | 代表题 |
|---|---|---|
| 相向收缩 | left、right 围出未处理区间；由配对、排序或上界决定移动哪侧 | 344、125、11、15、42 |
| 双序列协作 | 各自消费输入；交替消费、相等时推进或每次选取最值 | 1768、392、88 |
| 同向读写 | read 检查候选；write 只在保留时推进 | 27、26、283 |
| 多边界划分 | 边界分隔已知与未知区；看换回元素是否已知 | 75 |
| 连续匹配 | 文本位置与已匹配模式长度；朴素重试或前后缀回退 | 28 |
写代码前的四个问题
- 每个指针代表什么：当前元素、下一位置、有效长度，还是已匹配长度？
- 哪些区间已确定：统一 [left,right] 或 [left,right)，写出空区间条件。
- 为什么可以这样移动：用不变量或上界证明，避免仅凭示例猜规则。
- 每轮至少推进哪个量：未处理区间是否严格缩短？总推进次数是否有界？
Python 实现约定
- 所有 Python 答案均包含独立
class Solution和原题方法名；数组注解显式导入List。一次只复制一个解法提交。 - 区分原地修改并返回 None、返回有效长度、返回新结果三种接口。
- 切片、sorted 会分配内存；nums.sort() 虽原地修改，最坏仍可能使用 O(n) 辅助空间。
- 字符串不可变，拼接优先列表加 join；Python 负下标会访问末尾，必须显式保护边界。
- 空间分析区分辅助空间和输出空间；双串题会单独说明 m、n。
核心模板：先选推进模型
下面是语言无关的伪代码，用于记忆控制结构，不可直接提交。每道题卡片均有完整的可提交 Python 代码。
left ← 0, right ← n−1
while left < right:
先处理或评估当前边界
依据证明推进 left 或 right（或同时推进）
// 不要默认每轮都移动两边i ← 0, j ← 0
while 任一序列仍有未消费元素:
先判断各自边界
按交替、匹配、最值规则消费元素
至少推进一个消费游标write ← 0
for read 从 0 到 n−1:
if 当前候选应保留:
数组[write] ← 数组[read]
write ← write + 1
返回 write；若题目要求完整尾部，再补尾部维护：已知区 + 未知区 + 已知区
while 未知区非空:
判断当前位置元素
从已知区换回的值：按不变量推进
从未知区换回的值：先重查，再决定推进j ← 已匹配模式长度
while j > 0 且当前字符不匹配:
j ← prefix[j−1]
若当前字符匹配：j ← j+1
若 j 达到模式长度：得到完整匹配指针实验室：每一步都有依据
先预测下一步，再按按钮核对。演示与正文使用同样的移动规则，离线可运行。
STAGE 01 / 05相向指针入门
阶段目标：定义未处理区间，明确相遇时为什么停止。
01LEETCODE 344反转字符串
题意与接口
给定字符列表 s，直接修改这个列表，使字符顺序反转。函数不返回结果，额外空间必须为 O(1)。输入是可修改的列表，并非 Python 的不可变字符串。
解法一：两端交换（推荐）
解题思路与正确性
- 让
left、right分别指向首尾。未处理区间为闭区间 [left, right]。 - 交换两端元素后，这两个位置就与最终答案一致；同时向中间移动。
- 当 left ≥ right 时没有需要交换的不同位置；奇数长度的中点无需操作。
from typing import List
class Solution:
def reverseString(self, s: List[str]) -> None:
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
关键代码解释
while left < right：避免重复交换，也避免单元素自交换。- Python 多重赋值先计算右侧两个值，再写回左侧位置，不需要额外数组。
- 方法隐式返回
None，判题机检查传入列表是否改变。
示例推演
| 轮次 | left / right | 交换后 s |
|---|---|---|
| 初始 | 0 / 4 | [h, e, l, l, o] |
| 1 | 0 / 4 | [o, e, l, l, h] |
| 2 | 1 / 3 | [o, l, l, e, h] |
| 结束 | 2 / 2 | 原列表成为 [o, l, l, e, h]；返回 None |
时间复杂度
O(n)：最多交换 ⌊n/2⌋ 次。
空间复杂度
O(1)：仅使用两个下标和常数个临时引用。
选择与比较：手动交换能展示双指针；s.reverse() 也原地反转，但面试时应能写出其核心过程。
边界核对
| 输入 | 预期结果 |
|---|---|
| ["a"] | 保持 ["a"]，返回 None |
| ["a","b"] | 变成 ["b","a"] |
| []（扩展边界） | 保持 []，循环不会进入 |
易错点
s = s[::-1]只重绑定局部变量，外部列表没有改变。s[:] = s[::-1]虽能修改原列表，右侧切片仍需 O(n) 空间。- 不要把本题写成返回一个新字符串。
02LEETCODE 125验证回文串
题意与接口
忽略非字母数字字符，并将字母视为小写后，判断字符串是否正反一致。只包含空格、标点时，过滤后的空串也算回文。原题字符范围为可打印 ASCII。
解法一：跳过无效字符（推荐）
解题思路与正确性
- 从首尾向内寻找有效的字母或数字，标点和空格直接越过。
- 将两端有效字符转为小写比较；一旦不等，立即返回 False。
- 匹配成功才收缩两侧；直到所有有效字符配对成功。
class Solution:
def isPalindrome(self, s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
关键代码解释
isalnum()同时保留字母和数字，不能仅调用isalpha()。- 内层循环也要检查
left < right，防止连续标点让下标越界。 - 在原题 ASCII 范围内，每次
lower()处理一个字符，成本是 O(1)。Unicode 的大小写折叠规则不属于本题范围。
示例推演
| 步骤：s = "A,b:a" | left / right | 动作 |
|---|---|---|
| 初始 | 0 / 4 | A 与 a：转小写相同 |
| 收缩并跳过 | 1 / 3 → 2 / 2 | 逗号、冒号不参与比较 |
| 结束 | 2 / 2 | 中点 b，无需配对；返回 True |
时间复杂度
O(n)：两个指针各自单调移动，嵌套 while 不会导致 O(n²)。
空间复杂度
O(1)：没有构造过滤后的字符串。
选择与比较：适合严格常数空间；相较预处理，边界判断更多。
解法二：先过滤，再逆序比较
解题思路与正确性
将“字符选择”和“回文判断”分开。先形成只包含小写字母数字的序列，再与其逆序比较。它与双指针的比较规则相同，但显式保存了中间结果。
class Solution:
def isPalindrome(self, s: str) -> bool:
cleaned = "".join(ch.lower() for ch in s if ch.isalnum())
return cleaned == cleaned[::-1]
关键代码解释
join一次性拼接，避免循环中反复+=。[::-1]生成逆序副本，因此不能声称 O(1) 空间。
示例推演
"A,b:a" → "aba" → "aba" == "aba" → True。"0P" → "0p"，逆序为 "p0"，返回 False。
时间复杂度
O(n)：过滤、逆序和比较均为线性。
空间复杂度
O(n)：保存过滤串与逆序副本。
选择与比较：代码最简洁，适合快速验证；空间要求严格时选解法一。
边界核对
| 输入 | 预期结果 |
|---|---|
| " " 或 "!!!" | True |
| "race a car" | False |
| "A man, a plan, a canal: Panama" | True |
| "0P" | False |
易错点
- 数字不能忽略："0P" 应为 False。
- 过滤后为空串时返回 True。
- 不能直接比较未经归一化的字符，也不要对原字符串直接逆序判断。
STAGE 02 / 05双序列协作
阶段目标：覆盖任一输入先结束，并解释从后写的原因。
03LEETCODE 1768交替合并字符串
题意与接口
依次从 word1、word2 各取一个字符，从 word1 开始交替合并；某个字符串先结束时，保留另一个字符串的所有剩余字符，返回合并字符串。
解法一：两个独立游标
解题思路与正确性
- i、j 分别表示两个字符串中下一个未使用的位置。
- 只要任一字符串仍有字符，循环就继续；每轮先尝试 word1，再尝试 word2。
- 各自用边界判断保护取字符操作；这样某一方用尽后，另一方自然追加尾部。
class Solution:
def mergeAlternately(self, word1: str, word2: str) -> str:
i = j = 0
parts = []
while i < len(word1) or j < len(word2):
if i < len(word1):
parts.append(word1[i])
i += 1
if j < len(word2):
parts.append(word2[j])
j += 1
return "".join(parts)
关键代码解释
or保证长字符串尾部不丢失。若使用and，必须再补两个尾部循环。- 先处理 word1 的分支决定了交替起点。
- 字符串不可变；使用列表加
join让总拼接成本可控。
示例推演
| 轮次：ab / pqrs | i / j（轮后） | parts 合并视图 |
|---|---|---|
| 1 | 1 / 1 | ap |
| 2 | 2 / 2 | apbq |
| 3 | 2 / 3 | apbqr |
| 4 | 2 / 4 | apbqrs → 返回 "apbqrs" |
时间复杂度
O(m+n)：m、n 分别是两个字符串长度。
空间复杂度
O(m+n)：字符列表及最终结果；即使不计返回值，列表仍占线性空间。
选择与比较：两个指针最直观；同步前进时可合并成一个下标，但不改变复杂度。
边界核对
| 输入 | 预期结果 |
|---|---|
| "abc", "pqr" | "apbqcr" |
| "abcd", "pq" | "apbqcd" |
| "", "x"（扩展边界） | "x" |
易错点
- 直接使用
zip(word1, word2)会截断较长一方。 - 反复拼接不可变字符串可能导致二次时间；优先列表加 join。
- 不要把第二个 if 写为 elif，否则不能在同一轮依次取两边。
04LEETCODE 392判断子序列
题意与接口
判断 s 的字符能否按原相对次序出现在 t 中，允许跳过 t 中的字符，不要求连续。例如 "ace" 是 "abcde" 的子序列，"aec" 不是。空串是任意字符串的子序列。
解法一：单次查询双指针（推荐）
解题思路与正确性
- i 表示 s 中已匹配字符数，也是下一个待匹配位置；t 的循环游标不断向右。
- 遇到下一个需要的字符就立即匹配，否则仅跳过 t 的当前字符。
- 扫描结束，检查 i 是否等于 s 的长度。
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i = 0
for ch in t:
if i < len(s) and s[i] == ch:
i += 1
return i == len(s)
关键代码解释
i < len(s)必须放在s[i]前面，利用 and 短路避免空串或已匹配完成时越界。- 循环遍历 t，只有相等时才推进 s；两边都无条件前进会漏掉跳跃匹配。
- 最终比较匹配长度；不能仅因为某一次匹配成功就返回 True。
示例推演
| t = ahbgdc；s = abc | i（处理后） | 已匹配 |
|---|---|---|
| a | 1 | a |
| h | 1 | a |
| b | 2 | ab |
| g、d | 2 | ab |
| c | 3 | abc；返回 True |
时间复杂度
O(n)：n = len(t)，这份代码始终遍历整个 t；m = len(s)。
空间复杂度
O(1)：仅保存匹配下标。
选择与比较：单次查询最合适；匹配完提前 return 可减少实际工作，但最坏时间仍为 O(n)。
解法二：位置表 + 二分（大量查询的基础）
解题思路与正确性
预先记录 t 中每个字符出现的有序下标列表。对 s 的每个字符，用二分找第一个不小于 next_pos 的位置，然后将可用位置推进到它之后。若没有可用位置，匹配失败。
from bisect import bisect_left
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
positions = {}
for i, ch in enumerate(t):
positions.setdefault(ch, []).append(i)
next_pos = 0
for ch in s:
indexes = positions.get(ch, [])
k = bisect_left(indexes, next_pos)
if k == len(indexes):
return False
next_pos = indexes[k] + 1
return True
关键代码解释
bisect_left(indexes, next_pos)找到第一个合法下标的列表位置，不是 t 中的实际位置。next_pos = indexes[k] + 1保证同一位置不能重复使用。- 每个下标只存一次，所以位置表总空间为 O(n)。
示例推演
t="ahbgdc" 的位置表中 a:[0]、b:[2]、c:[5]。查询 "abc" 依次找到 0、2、5，next_pos 为 1、3、6，返回 True；查询 "axc" 在 x 的空列表处返回 False。
时间复杂度
单次 O(n + m log(n+1))；复用预处理后每次查询 O(m log(n+1))，预处理 O(n)。
空间复杂度
O(n)：位置表；单次查询额外游标为 O(1)。
选择与比较：多次查询更有价值。固定小写字母表还可建 next 表，以 O(26n) 预处理和空间换取每次 O(m) 查询；本册保留位置表的完整实现。
边界核对
| 输入 | 预期结果 |
|---|---|
| "", "abc" | True |
| "a", "" | False |
| "aa", "ab" | False |
| "axc", "ahbgdc" | False |
易错点
- 子序列允许不连续，子串必须连续，不能混为一谈。
- s 比 t 长时必定 False；不做长度预判也不影响正确性。
- 同一字符的多个副本必须占用不同且递增的位置。
05LEETCODE 88合并两个有序数组
题意与接口
nums1 的总长度为 m+n，只有前 m 个元素有效，末尾 n 个位置用于容纳 nums2。将长度为 n 的 nums2 合并到 nums1，保持非递减顺序，原地修改并返回 None。末尾占位零不参与比较；有效数据中也可以有零。
解法一：从后向前填充（推荐）
解题思路与正确性
- 两条有序前缀的最大值一定在各自末端。i、j 指向末端，write 指向可写的最后位置。
- 每次把较大元素写到 write，再移动对应读指针和 write。
- 只需保证 nums2 全部放入；若 nums2 先耗尽，nums1 剩余前缀本来就在正确位置。
from typing import List
class Solution:
def merge(self, nums1: List[int], m: int,
nums2: List[int], n: int) -> None:
i, j, write = m - 1, n - 1, m + n - 1
while j >= 0:
if i >= 0 and nums1[i] > nums2[j]:
nums1[write] = nums1[i]
i -= 1
else:
nums1[write] = nums2[j]
j -= 1
write -= 1
关键代码解释
i >= 0必须先判断，Python 负索引会读到末尾数据而非报错。- 当 i < 0 时，else 分支把 nums2 剩余元素依次放入。
- 相等时从 nums2 取值不影响数值有序性；因为从后向前写，nums1 中的相同值会排在它前面。
示例推演
| i / j / write（写入前） | 选取 | nums1 写入后的状态 |
|---|---|---|
| 2 / 2 / 5 | 6 | [1,2,3,0,0,6] |
| 2 / 1 / 4 | 5 | [1,2,3,0,5,6] |
| 2 / 0 / 3 | 3 | [1,2,3,3,5,6] |
| 1 / 0 / 2 | 2（nums2） | [1,2,2,3,5,6]；j=-1 结束 |
时间复杂度
O(m+n)：每次确定一个最终位置；n=0 时直接结束。
空间复杂度
O(1)：没有新数组，也没有列表切片。
选择与比较：原地且线性；需要同时管理两个读位置和一个写位置。
解法二：正向合并到临时列表
解题思路与正确性
像归并排序的合并步骤一样，每次取两边尚未使用的最小值放入新列表，读完后整体写回 nums1。临时列表让读取与写入分离，避免覆盖。
from typing import List
class Solution:
def merge(self, nums1: List[int], m: int,
nums2: List[int], n: int) -> None:
i = j = 0
merged = []
while i < m or j < n:
if j == n or (i < m and nums1[i] <= nums2[j]):
merged.append(nums1[i])
i += 1
else:
merged.append(nums2[j])
j += 1
nums1[:] = merged
关键代码解释
j == n优先处理 nums2 已耗尽的情况。nums1[:] = merged修改原列表；不能写成nums1 = merged。
示例推演
对 [1,2,3] 与 [2,5,6]，依次选取 1、2（nums1）、2（nums2）、3、5、6；merged 成为 [1,2,2,3,5,6]，最后写回 nums1。
时间复杂度
O(m+n)。
空间复杂度
O(m+n)：临时合并结果。
选择与比较：逻辑更直观，适合作为归并模板；空间优于排序合并与否需单独分析，严格 O(1) 要用逆向法。
边界核对
| 输入 | 预期结果 |
|---|---|
| nums1=[0], m=0；nums2=[1], n=1 | nums1 → [1] |
| nums1=[1], m=1；nums2=[], n=0 | 保持 [1] |
| nums1=[-1,0,0], m=2；nums2=[0], n=1 | nums1 → [-1,0,0] |
易错点
- 不能从前向后直接写 nums1，否则会覆盖还未读到的原数据。
- m 和 n 表示有效数据个数，不能用 nums1 中零的位置识别占位区。
- 题目要求修改 nums1，返回一个新列表无法满足接口。
STAGE 03 / 05同向读写与稳定划分
阶段目标：区分有效长度、物理长度与保序要求。
06LEETCODE 27移除元素
题意与接口
原地处理 nums，返回不等于 val 的元素数量 k，并让前 k 个位置包含这些元素。原题允许改变元素顺序；k 之后的数据无需清空，列表物理长度无需缩短。
解法一：稳定过滤（通用模板）
解题思路与正确性
- read 扫描输入，write 是下一个有效元素写入的位置，也等于已保留元素个数。
- 若当前元素不等于 val，把它写入 nums[write]，再增加 write；否则只移动 read。
- 返回 write；前 write 个位置就是答案，其余位置忽略。
from typing import List
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
write = 0
for read in range(len(nums)):
if nums[read] != val:
nums[write] = nums[read]
write += 1
return write
关键代码解释
- 写入后才
write += 1，否则会遗漏下标 0。 - 没有调用 remove 或 pop，不会造成反复移动后缀。
return write返回长度，而非最后一个元素下标。
示例推演
| read：nums=[3,2,2,3], val=3 | 动作 | 有效前缀 |
|---|---|---|
| 0 | 跳过 3 | [] |
| 1 | nums[0]=2；write=1 | [2] |
| 2 | nums[1]=2；write=2 | [2,2] |
| 3 | 跳过 3；返回 2 | 物理列表 [2,2,2,3]，只看前 2 项 |
时间复杂度
O(n)：每个元素读取一次。
空间复杂度
O(1)。
选择与比较：保持顺序、可复用；即使无须保持顺序，也通常优先写这个易证明的版本。
解法二：末尾替换（允许乱序时）
解题思路与正确性
维护仍待处理的半开区间 [i, end)。遇到 val 就用区间末尾元素覆盖它，再缩短有效范围；换来的元素没有被检查，所以 i 不动。只有遇到合法元素时才推进 i。
from typing import List
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i, end = 0, len(nums)
while i < end:
if nums[i] == val:
end -= 1
nums[i] = nums[end]
else:
i += 1
return end
关键代码解释
end是有效长度，末尾元素在end - 1，所以先减再取。- 覆盖后不能无条件 i += 1，因为换来的数也可能是 val。
示例推演
[3,2,2,3]：i=0,end=4，先用末尾 3 覆盖并令 end=3；再用下标 2 的 2 覆盖并令 end=2，得到 [2,2,2,3]。随后 i 从 0 走到 2，返回 2。
时间复杂度
O(n)。
空间复杂度
O(1)。
选择与比较：写操作次数等于被移除元素数，val 很少时有优势；无法保留原有顺序，因此不能直接用于移动零或稳定去重。
边界核对
| 输入 | 预期结果 |
|---|---|
| [], val=1 | k=0 |
| [2,2], val=2 | k=0 |
| [1,2], val=3 | k=2，前缀 [1,2] |
易错点
- 不必真的删掉尾部元素；只返回 k 并保证前 k 项正确。
- 遍历中调用 nums.remove 会改变下标关系，也可能退化为 O(n²)。
- 末尾替换版在替换后必须重查当前位置。
07LEETCODE 26删除有序数组中的重复项
题意与接口
给定非递减数组，原地保留每种值的一次出现，返回不同元素个数 k。前 k 个位置必须按原来的非递减顺序存储唯一值，k 之后内容忽略。
解法一：与有效前缀末尾比较
解题思路与正确性
- 有序数组中相同值必然连续，因此只需和最后一个保留值比较。
- 有效前缀为空，或当前值不同于最后保留值时，才执行写入。
- read 始终前进，write 只在遇到新值时增加；结束后 write 即唯一值个数。
from typing import List
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
write = 0
for read in range(len(nums)):
if write == 0 or nums[read] != nums[write - 1]:
nums[write] = nums[read]
write += 1
return write
关键代码解释
write == 0 or ...先短路保护nums[write-1]，也自然兼容空列表。- 与“最后保留元素”比较比依赖原相邻下标更容易推广。
- write ≤ read，所以覆盖发生在已读区或当前位置。
示例推演
| read：nums=[1,1,2,2,3] | 判断 | 有效前缀 |
|---|---|---|
| 0 | write=0，保留 | [1] |
| 1 | 1 等于末尾 1，跳过 | [1] |
| 2 | 2 不等于末尾 1，保留 | [1,2] |
| 3 | 2 等于末尾 2，跳过 | [1,2] |
| 4 | 3 不等于末尾 2，保留 | [1,2,3]；k=3 |
时间复杂度
O(n)。
空间复杂度
O(1)：没有集合或新列表。
选择与比较：有序性把“见过没有”简化成一次末尾比较。若变为每个值最多保留 K 次，保留条件可推广为 write < K 或 nums[read] != nums[write-K]，但本题 K=1。
边界核对
| 输入 | 预期结果 |
|---|---|
| [1,1,1] | k=1，前缀 [1] |
| [1,2,3] | k=3，前缀不变 |
| [-1,-1,0,0,2] | k=3，前缀 [-1,0,2] |
| []（扩展边界） | k=0 |
易错点
- 若数组无序，相同元素不一定相邻，本方法不能用于全局去重。
- 返回 write，不是 write-1。
- 不能用 sorted(set(nums)) 替代要求的常数空间原地过程。
08LEETCODE 283移动零
题意与接口
将所有 0 移到数组末尾，并保持非零元素原有相对顺序。必须原地修改 nums，返回 None；不能复制整个数组。
解法一：压缩非零，再补零
解题思路与正确性
先用稳定过滤把非零元素压到前面。与移除元素不同，本题要保留整个列表长度并指定尾部为零，所以扫描结束后还要把 [write, n) 全部设为 0。
from typing import List
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
write = 0
for read in range(len(nums)):
if nums[read] != 0:
nums[write] = nums[read]
write += 1
for i in range(write, len(nums)):
nums[i] = 0
关键代码解释
- 只在读完后统一补零；提前清空尚未读取的位置会丢数据。
- 末尾补零用循环，无需构造
[0] * k临时列表。
示例推演
| 阶段：[0,1,0,3,12] | write | 数组（含尚无意义的尾部） |
|---|---|---|
| 读取 0 | 0 | [0,1,0,3,12] |
| 读取 1 | 1 | [1,1,0,3,12] |
| 读取 3 | 2 | [1,3,0,3,12] |
| 读取 12 | 3 | [1,3,12,3,12] |
| 补零 | 3 | [1,3,12,0,0]；返回 None |
时间复杂度
O(n)：两遍循环总迭代数不超过 2n。
空间复杂度
O(1)。
选择与比较：最好理解；数组即使无零，第一遍也会发生自赋值。
解法二：交换到首个空位（一次扫描）
解题思路与正确性
维护非零区 [0, write)、零区 [write, read) 与未读区 [read, n)。遇到非零元素时，把它与零区首位交换。若 write==read，说明中间没有零，直接跳过自交换。
from typing import List
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
write = 0
for read in range(len(nums)):
if nums[read] != 0:
if write != read:
nums[write], nums[read] = nums[read], nums[write]
write += 1
关键代码解释
- 交换后原来的 read 位置变成零，不需要另补尾部。
- 每次选中的是输入中下一个非零元素，因此非零顺序保持不变。
- 跳过自交换可以减少无零前缀上的写入，但一次交换通常包含两次列表写入，并不意味着任何输入都比补零版写得少。
示例推演
[0,1,0,3,12] 依次交换 (0,1)、(1,3)、(2,4)：[1,0,0,3,12] → [1,3,0,0,12] → [1,3,12,0,0]。write 最终为 3。
时间复杂度
O(n)：一次 read 扫描。
空间复杂度
O(1)。
选择与比较：无需第二遍，能跳过自交换；与补零法在具体写操作次数上的优劣取决于数据分布。
边界核对
| 输入 | 预期结果 |
|---|---|
| [0,0,0] | [0,0,0] |
| [1,2,3] | 保持 [1,2,3] |
| [0,1,0,1] | [1,1,0,0] |
易错点
- “非零元素稳定”是硬要求，不能随意拿末尾元素替换零。
- 只压缩非零但不补尾部，会留下旧的非零值。
- 不能构造非零列表后再拼零冒充 O(1) 空间。
STAGE 04 / 05候选排除与有序搜索
阶段目标：证明短板移动与有序和的移动方向。
09LEETCODE 11盛最多水的容器
题意与接口
height[i] 表示位于横坐标 i 的竖线高度。选两条竖线，与横轴构成容器，返回最大面积。宽度是下标差，内部其他线段不占据水的体积；这与接雨水的柱子模型不同。
解法一：枚举所有边界（对照用）
解题思路与正确性
完整枚举每一对不同下标，计算面积并取最大。它不会漏解，可用于小输入的正确性对照；原题大规模输入应使用下一种线性算法。
from typing import List
class Solution:
def maxArea(self, height: List[int]) -> int:
best = 0
for left in range(len(height)):
for right in range(left + 1, len(height)):
area = (right - left) * min(height[left], height[right])
best = max(best, area)
return best
关键代码解释
- right 从 left+1 开始，保证宽度为正并避免重复枚举。
- 面积只看两个端点与它们的距离。
示例推演
对 [1,2,1]，三对边界 (0,1)、(0,2)、(1,2) 的面积依次为 1、2、1，最大值为 2。
时间复杂度
O(n²)：共有 n(n−1)/2 对。
空间复杂度
O(1)。
选择与比较：易验证但可能超时，不能把它当作原题高效提交方案。
解法二：每次舍弃较短边（推荐）
解题思路与正确性
- 从最宽的两端开始，先计算当前面积。
- 若左边较短，就丢弃左边；否则丢弃右边。
- 持续取最大值，直到两指针相遇。
from typing import List
class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
best = 0
while left < right:
area = (right - left) * min(height[left], height[right])
best = max(best, area)
if height[left] <= height[right]:
left += 1
else:
right -= 1
return best
关键代码解释
- 必须先算面积再移动，否则会跳过最外层候选。
- 较高边保持不动是因为短边限制水高；只移动高边不能突破当前短板。
- 数组无需有序，单调性来自候选面积的上界，而不是高度排序。
示例推演
| height=[1,8,6,2,5,4,8,3,7] | 面积 | 动作 |
|---|---|---|
| left=0,right=8 | 8×1=8 | 左短，left→1 |
| left=1,right=8 | 7×7=49 | 右短，right→7 |
| left=1,right=7 | 6×3=18 | right→6 |
| left=1,right=6 | 5×8=40 | 等高，本实现 left→2 |
| 继续收缩到相遇 | 后续无更大面积 | 返回 49 |
时间复杂度
O(n)：每轮 left 或 right 移动一次。
空间复杂度
O(1)。
选择与比较：线性且空间常数；关键能力是解释为什么舍弃短边不漏最优解。
边界核对
| 输入 | 预期结果 |
|---|---|
| [1,1] | 1 |
| [0,0] | 0 |
| [1,2,1] | 2 |
| [4,3,2,1,4] | 16 |
易错点
- 宽度为 right-left，不能加 1。
- 面积不能用两边最大高度，必须用 min。
- 遇到等高可以移动一边；不要漏掉当前面积。
10LEETCODE 15三数之和
题意与接口
找出 nums 中所有和为 0 的三元组，三个元素必须来自不同下标。答案按数值组合去重；相同值可来自不同位置，例如 [0,0,0] 是合法三元组。返回顺序不限。
解法一：排序 + 固定锚点 + 双指针（推荐）
解题思路与正确性
- 排序后固定 i，把问题变成：在右侧后缀中找两个和为 -nums[i] 的数。
- 总和偏小，增大 left；总和偏大，减小 right。有序性保证可按方向排除候选。
- 遇到 0 时记录答案，移动两边并跳过重复值；外层也跳过相同锚点。
from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
answer = []
n = len(nums)
for i in range(n - 2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
answer.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
return answer
关键代码解释
nums[i] > 0才能提前结束；等于 0 时仍可能有 [0,0,0]。- 成功后先移动，再用
left-1与right+1跳过刚刚使用的值。 nums.sort()会修改传入列表；若必须保留输入，改为nums = sorted(nums)，并计入复制空间。- 固定 i 的每次扫描 O(n)，总计 O(n²)；Python 的原地 sort 在最坏情况下仍可能使用 O(n) 辅助空间。
示例推演
| 排序后 [-4,-1,-1,0,1,2] | left / right | 动作 |
|---|---|---|
| i=0，值 -4 | 1 / 5 起 | 所有和偏小，本轮无解 |
| i=1，值 -1 | 2 / 5 | -1-1+2=0，记录 [-1,-1,2] |
| 仍 i=1 | 3 / 4 | -1+0+1=0，记录 [-1,0,1] |
| i=2，值 -1 | — | 重复锚点跳过 |
| i=3，值 0 | 4 / 5 | 和为 3，缩右后相遇；最终两个组合 |
时间复杂度
O(n²)：排序 O(n log n)，n 次线性扫描占主导。
空间复杂度
辅助 O(n)：按 Python 排序最坏空间计；双指针本身 O(1)。另有 O(k) 输出，k 为答案三元组数量，最坏 O(n²)。
选择与比较：推荐面试方案；若只分析扫描阶段，辅助空间为 O(1)，但不能忽略 Python sort 的实现成本。
解法二：固定一个数 + 哈希查找
解题思路与正确性
固定 i，向右枚举 j，用 seen 存储 i 和 j 之间已扫描的数，寻找补数 need。将三元组规范成有序元组放入答案集合，从而去重。这里排序的永远只有 3 个数，是常数工作。
from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
answer = set()
for i in range(len(nums) - 2):
seen = set()
for j in range(i + 1, len(nums)):
need = -nums[i] - nums[j]
if need in seen:
answer.add(tuple(sorted((nums[i], need, nums[j]))))
seen.add(nums[j])
return [list(triple) for triple in answer]
关键代码解释
- 先查询后加入 seen，保证补数来自更早的另一位置，避免重复使用 nums[j]。
- seen 每个 i 都必须重新创建。
- 答案用集合去重，最终转回列表以满足提交返回类型。
示例推演
nums=[-1,0,1,2,-1,-4]：固定首个 -1，j=1 时 seen={0}；j=2 的值 1 需要 0，得到 (-1,0,1)；j=4 的值 -1 需要 2，得到 (-1,-1,2)。其他轮次生成的相同元组由 answer 集合消除。
时间复杂度
平均 O(n²)：假设集合查询与插入平均 O(1)；哈希冲突严重时不保证同样界。
空间复杂度
辅助 O(n)，另有 O(k) 答案集合与返回列表。
选择与比较：保留输入且易连接两数之和思路；答案集合与重复扫描带来额外常数，排序双指针更便于系统去重。
边界核对
| 输入 | 预期结果 |
|---|---|
| [0,0,0,0] | [[0,0,0]] |
| [0,1,1] | [] |
| [-2,0,0,2,2] | [[-2,0,2]] |
| []、[1,2]（扩展边界） | [] |
易错点
- 不能先 set(nums)，那会丢掉重复值的数量，例如 [-1,-1,2]。
- 外层去重和成功后的左右去重各有职责，不能只做一种。
- 成功后必须移动指针，否则陷入死循环。
- 剪枝依赖已排序：排序前不能用 nums[i]>0 判断无解。
STAGE 05 / 05进阶边界与匹配
阶段目标：解释未知区、可结算位置与失配回退。
11LEETCODE 75颜色分类
题意与接口
数组只包含 0、1、2，原地排列为所有 0 在前、1 居中、2 在后。不能调用内置 sort；进阶要求常数额外空间和一趟扫描，返回 None。
解法一：计数后写回
解题思路与正确性
先统计三个值的个数，再按 0、1、2 的顺序写回。值域恒为 3，所以计数数组是常数空间。它需要两阶段遍历，满足基础要求，不满足一趟扫描的进阶目标。
from typing import List
class Solution:
def sortColors(self, nums: List[int]) -> None:
counts = [0, 0, 0]
for value in nums:
counts[value] += 1
write = 0
for value in range(3):
for _ in range(counts[value]):
nums[write] = value
write += 1
关键代码解释
- counts 长度固定为 3，与输入长度无关。
- 写回的内层循环总次数为 n，不是 3n²。
示例推演
[2,0,2,1,1,0] → counts=[2,2,2] → 写两个 0、两个 1、两个 2，得到 [0,0,1,1,2,2]。
时间复杂度
O(n)：统计 n 次、写回 n 次。
空间复杂度
O(1)：只用三个计数。
选择与比较：最易实现和核验，适合对照；无法体现一趟扫描的区间维护。
解法二：三路划分（进阶推荐）
解题思路与正确性
- 遇到 0：与 low 交换，0 区扩大；low 原先若在 current 之前，其值必为 1，换回来的值已经确定，因此 current 可推进。
- 遇到 1：它直接进入中间 1 区，current 前进。
- 遇到 2：与 high 交换并缩小 high；换回来的元素原属于未知区，必须留在当前位置重新检查。
from typing import List
class Solution:
def sortColors(self, nums: List[int]) -> None:
low = current = 0
high = len(nums) - 1
while current <= high:
if nums[current] == 0:
nums[low], nums[current] = nums[current], nums[low]
low += 1
current += 1
elif nums[current] == 1:
current += 1
else:
nums[current], nums[high] = nums[high], nums[current]
high -= 1
关键代码解释
current <= high包含最后一个未知元素。- 与 high 交换后不能 current += 1，否则可能漏掉换来的 0。
- low、current、high 是三条边界；“双指针专题”也包含由多个边界扩展的原地划分思想。
示例推演
| low / current / high（处理前） | 动作 | 数组（处理后） |
|---|---|---|
| 0 / 0 / 5 | 2 换到尾部，high→4 | [0,0,2,1,1,2] |
| 0 / 0 / 4 | 0 自交换，low/current→1 | [0,0,2,1,1,2] |
| 1 / 1 / 4 | 0 自交换，low/current→2 | [0,0,2,1,1,2] |
| 2 / 2 / 4 | 2 与尾端 1 交换，high→3 | [0,0,1,1,2,2] |
| 2 / 2 / 3 → 2 / 3 / 3 | 两次遇到 1，current→4 | 未知区空，返回 None |
时间复杂度
O(n)：未知区间每轮缩短一个位置。
空间复杂度
O(1)。
选择与比较：一趟完成原地划分；区间定义比背诵 if 分支更重要。算法对带有额外身份信息的对象并不保证稳定。
边界核对
| 输入 | 预期结果 |
|---|---|
| [2,0,1] | [0,1,2] |
| [2,2,2] | 保持 [2,2,2] |
| [0] | 保持 [0] |
| []（扩展边界） | 保持 [] |
易错点
- 遇到 2 只缩 high，不移动 current。
- 不能把循环写成 current<high，否则最后一个未知位置未检查。
- 一趟扫描不等于每个位置只访问一次，而是整体操作数线性、无需重新遍历整数组。
12LEETCODE 42接雨水
题意与接口
给定非负柱高数组，每根柱子宽为 1，求柱间能积存的总水量。柱子本身占据空间；每个位置的水量取决于两侧能形成的最高边界，而非只选两个端点。
解法一：前后缀最大值（理解公式）
解题思路与正确性
分别预计算每个位置左侧（含自身）和右侧（含自身）的最高柱子。水位由较矮的边界决定，再减去本柱高度。因为最大值包含自身，差值天然非负。
from typing import List
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
if n == 0:
return 0
left_max = [0] * n
right_max = [0] * n
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i - 1], height[i])
right_max[-1] = height[-1]
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], height[i])
water = 0
for i in range(n):
water += min(left_max[i], right_max[i]) - height[i]
return water
关键代码解释
- left_max 与 right_max 都含当前位置，所以首尾贡献为 0。
- 右侧扫描方向必须从 n-2 向 0，保证 right_max[i+1] 已计算。
- 先判断空数组再访问首尾下标。
示例推演
| height=[4,2,0,3,2,5] | 各位置值 |
|---|---|
| left_max | [4,4,4,4,4,5] |
| right_max | [5,5,5,5,5,5] |
| 逐列水量 | [0,2,4,1,2,0] |
| 总水量 | 9 |
时间复杂度
O(n)：三次线性遍历。
空间复杂度
O(n)：两个长度 n 的最大值数组。
选择与比较：公式直观，适合先掌握并作为双指针的正确性对照。
解法二：比较两侧最高边界（推荐）
解题思路与正确性
- 保留尚未结算的闭区间 [left, right]；每轮先把当前边界柱计入两侧最高值。
- 若 left_max ≤ right_max，则左侧水位已经可以确定为 left_max，立即结算 left。
- 否则右侧水位确定为 right_max，结算 right。每轮只结算一个位置，直到区间为空。
from typing import List
class Solution:
def trap(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
left_max = right_max = 0
water = 0
while left <= right:
left_max = max(left_max, height[left])
right_max = max(right_max, height[right])
if left_max <= right_max:
water += left_max - height[left]
left += 1
else:
water += right_max - height[right]
right -= 1
return water
关键代码解释
- 先更新 max，再做减法，水量不会为负。
- 本实现比较
left_max与right_max，不要混搭另一种“比较当前柱高”的循环与更新顺序。 left <= right恰好把每个位置结算一次；空数组 right=-1，不进入循环。
示例推演
| left / right（结算前） | left_max / right_max | 本次新增 → 累计 |
|---|---|---|
| 0 / 5 | 4 / 5 | 左：4−4=0 → 0 |
| 1 / 5 | 4 / 5 | 左：4−2=2 → 2 |
| 2 / 5 | 4 / 5 | 左：4−0=4 → 6 |
| 3 / 5 | 4 / 5 | 左：4−3=1 → 7 |
| 4 / 5 | 4 / 5 | 左：4−2=2 → 9 |
| 5 / 5 | 5 / 5 | 左：5−5=0 → 9；结束 |
时间复杂度
O(n)：每轮结算一个位置。
空间复杂度
O(1)：两个极值、两个下标和累计水量。
选择与比较：由前后缀公式压缩而来，达到常数空间；务必解释为何只需较小的一侧极值。
解法三：单调栈按层结算
解题思路与正确性
栈内保存高度非递增的柱子下标。当前柱比栈顶高时，弹出的柱子是凹槽底部；新的栈顶是左边界，当前柱是右边界，按水平层计算新增水量。继续弹栈可结算更高层。
from typing import List
class Solution:
def trap(self, height: List[int]) -> int:
stack = []
water = 0
for right, h in enumerate(height):
while stack and h > height[stack[-1]]:
bottom = stack.pop()
if not stack:
break
left = stack[-1]
width = right - left - 1
depth = min(height[left], h) - height[bottom]
water += width * depth
stack.append(right)
return water
关键代码解释
- 存下标才能同时计算横向距离和纵向高度。
- 宽度减 1，排除左右两根边界柱。
- 栈高度允许相等；相等柱暂不弹出，后续可能产生深度为 0 的层，不影响结果。
示例推演
对 [4,2,0,3,2,5]：right=3（高 3）弹出下标 2（底 0），左界 1（高 2），新增 1×2=2；再弹下标 1，左界 0，新增 2×1=2，累计 4。right=5 先形成 1×1=1，再形成 4×1=4，累计 9。最后弹出最左柱时栈空，不结算。
时间复杂度
O(n)：每个下标入栈一次、出栈至多一次，内层 while 的总工作线性。
空间复杂度
O(n)：最坏递减数组时栈保存所有下标。
选择与比较：适合联系单调栈与凹槽结构；空间不如双指针，但能按层解释积水形成。
边界核对
| 输入 | 预期结果 |
|---|---|
| [0,1,0,2,1,0,1,3,2,1,2,1] | 6 |
| [4,2,0,3,2,5] | 9 |
| [1,2,3] 或 [3,2,1] | 0 |
| [2,0,2] | 2 |
| [] 或 [1]（含扩展边界） | 0 |
易错点
- 不能把本题直接写成最大容器面积，内部柱子占空间。
- 每列水位取两侧最高边界的 min，不能取 max。
- 只看相邻两柱不够，远处高柱也可能形成边界。
- 单调栈中计算宽度要减 1，弹栈后必须检查是否还有左边界。
13LEETCODE 28找出字符串中第一个匹配项的下标
题意与接口
给定 haystack 与 needle，返回 needle 在 haystack 中第一次完整连续出现的起始下标，找不到返回 -1。原题 needle 非空；代码额外约定空模式返回 0。本题要求连续，不能沿用子序列的跳跃匹配。
解法一：逐个起点尝试匹配
解题思路与正确性
- 按从小到大的顺序枚举起点 start，只有 start≤n-m 时后面才有足够空间。
- 用 j 同时推进模式下标和文本相对下标，逐个比较连续字符。
- 完整匹配就返回当前 start，天然保证第一次；失配则换下一个起点重新匹配。
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
n, m = len(haystack), len(needle)
if m == 0:
return 0
for start in range(n - m + 1):
j = 0
while j < m and haystack[start + j] == needle[j]:
j += 1
if j == m:
return start
return -1
关键代码解释
range(n-m+1)包含最后一个合法起点。m>n 时范围为空，自然返回 -1。- 不使用切片，所以每次匹配只需常数额外空间。
- 失配必须重置 j，从新的起点重新开始；不能仅跳过当前坏字符。
示例推演
haystack="aab", needle="ab"：start=0 时先匹配 a，第二位 a≠b，失败；start=1 时 a、b 均匹配，返回 1。若 needle="ac"，两个合法起点都失败，返回 -1。
时间复杂度
m≤n 时 O((n−m+1)m)，通常简记 O(nm)；m>n 时 O(1)。
空间复杂度
O(1)。
选择与比较：结构直观，适合建立连续匹配概念；重复前缀会导致大量重比。
解法二：KMP 前缀函数（进阶）
解题思路与正确性
prefix[i] 表示 needle[0:i+1] 的最长相等真前缀与后缀的长度；真前缀不能等于整个串。扫描文本时 j 表示已匹配的模式长度。失配后，无须让文本指针回退，只需把 j 调整到上一段可复用的前后缀长度。
- 构建 prefix：对每个 i，若 needle[i] 无法接在当前前缀后，就反复 j=prefix[j-1]。能接上则 j 加一，记为 prefix[i]。
- 搜索前将 j 重置为 0，逐字符扫描 haystack。失配时用同样的前后缀链回退 j。
- j 达到 m 时，模式末尾位于 i，起点为 i-m+1；马上返回，因此得到第一次匹配。
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
m = len(needle)
if m == 0:
return 0
prefix = [0] * m
j = 0
for i in range(1, m):
while j > 0 and needle[i] != needle[j]:
j = prefix[j - 1]
if needle[i] == needle[j]:
j += 1
prefix[i] = j
j = 0
for i, ch in enumerate(haystack):
while j > 0 and ch != needle[j]:
j = prefix[j - 1]
if ch == needle[j]:
j += 1
if j == m:
return i - m + 1
return -1
关键代码解释
- 构建 prefix 时 i 从 1 开始，prefix[0]=0。
- 回退是
j = prefix[j - 1]，不是 j-=1，也不是 prefix[j]。 - 回退用 while，不是 if，因为可能连续失配多次。
- prefix 存的是长度；j 既是已匹配长度，也是下一待比较模式下标，达到 m 后立即返回，避免下次访问 needle[m]。
示例推演
| needle="ababac" | prefix / j | 含义或动作 |
|---|---|---|
| 前缀表 | [0,0,1,2,3,0] | 末尾 c 与 b、b、a 均无法形成前后缀 |
| haystack="ababababac"，i=0..4 | j=5 | 已匹配 ababa |
| i=5，ch=b | j:5→3→4 | 先回退到长度 3，再匹配 b；文本 i 不回退 |
| i=6，ch=a | j=5 | 延长匹配 |
| i=7，ch=b | j:5→3→4 | 重复使用后缀 abab |
| i=8、9，ch=a、c | j:4→5→6 | 返回 9−6+1=4 |
时间复杂度
O(n+m)：前缀表 O(m)，文本扫描 O(n)，总回退次数也为线性。
空间复杂度
O(m)：保存前缀表。
选择与比较：重复前缀较多、文本较长时更稳定；实现与证明成本较高。工程上可用 haystack.find(needle)，面试需先说明原理，不能给其内置实现随意标注统一 O(nm) 或 O(n+m)。
边界核对
| 输入 | 预期结果 |
|---|---|
| "sadbutsad", "sad" | 0 |
| "leetcode", "leeto" | -1 |
| "abc", "c" | 2 |
| "abc", "abcd" | -1 |
| "ababababac", "ababac" | 4 |
| "abc", ""（扩展边界） | 0 |
易错点
- 子串要求连续，不能像判断子序列那样跳过中间文本字符后继续累计。
- 最后合法起点是 n-m，不能遗漏。
- KMP 搜索前必须将 j 重置为 0。
- 前缀函数是长度，不是最后下标；与使用 -1 哨兵的 next 数组写法不能混用。
知识点与复杂度速查
下表选取推荐解法（无推荐标记则取首个实现）；n、m 与输出空间的定义以题目卡片为准。
| 题目 | 知识点 | 时间 | 空间 |
|---|---|---|---|
| 344 · 反转字符串 | 相向指针 · 原地交换 · 闭区间 | O(n)：最多交换 ⌊n/2⌋ 次。 | O(1)：仅使用两个下标和常数个临时引用。 |
| 125 · 验证回文串 | 相向指针 · 字符过滤 · 大小写归一化 | O(n)：两个指针各自单调移动，嵌套 while 不会导致 O(n²)。 | O(1)：没有构造过滤后的字符串。 |
| 1768 · 交替合并字符串 | 双序列指针 · 尾部处理 · join | O(m+n)：m、n 分别是两个字符串长度。 | O(m+n)：字符列表及最终结果；即使不计返回值，列表仍占线性空间。 |
| 392 · 判断子序列 | 双序列扫描 · 贪心匹配 · 多次查询 | O(n)：n = len(t)，这份代码始终遍历整个 t；m = len(s)。 | O(1)：仅保存匹配下标。 |
| 88 · 合并两个有序数组 | 逆向双指针 · 额外写指针 · 防止覆盖 | O(m+n)：每次确定一个最终位置；n=0 时直接结束。 | O(1)：没有新数组，也没有列表切片。 |
| 27 · 移除元素 | 读写指针 · 有效前缀 · 稳定性 | O(n)：每个元素读取一次。 | O(1)。 |
| 26 · 删除有序数组中的重复项 | 有序性 · 读写指针 · 相邻去重 | O(n)。 | O(1)：没有集合或新列表。 |
| 283 · 移动零 | 稳定划分 · 非零前缀 · 原地交换 | O(n)：两遍循环总迭代数不超过 2n。 | O(1)。 |
| 11 · 盛最多水的容器 | 相向指针 · 贪心排除 · 短板证明 | O(n)：每轮 left 或 right 移动一次。 | O(1)。 |
| 15 · 三数之和 | 排序 · 固定一个数 · 相向扫描 · 三层去重 | O(n²)：排序 O(n log n)，n 次线性扫描占主导。 | 辅助 O(n)：按 Python 排序最坏空间计；双指针本身 O(1)。另有 O(k) 输出，k 为答案三元组数量，最坏 O(n²)。 |
| 75 · 颜色分类 | 三路划分 · 荷兰国旗 · 未知区间 | O(n)：未知区间每轮缩短一个位置。 | O(1)。 |
| 42 · 接雨水 | 前后缀极值 · 相向结算 · 单调栈 | O(n)：每轮结算一个位置。 | O(1)：两个极值、两个下标和累计水量。 |
| 28 · 找出字符串中第一个匹配项的下标 | 连续匹配 · 朴素双游标 · KMP 前缀函数 | m≤n 时 O((n−m+1)m)，通常简记 O(nm)；m>n 时 O(1)。 | O(1)。 |
面试决策与不变量对照
| 识别信号 | 优先考虑 | 证明重点 |
|---|---|---|
| 首尾比较或交换 | 相向指针 | 外侧已确定，中间无需重复处理 |
| 两个输入合并或匹配 | 双序列游标 | 每次消费下一合法字符或极值 |
| 原地过滤，前 k 位有效 | 读写指针 | 有效前缀正确，不覆盖未读数据 |
| 有序数组上的两数和 | 排序与相向扫描 | 和偏小舍左，和偏大舍右 |
| 最大容器 | 移动短边 | 固定短边的剩余候选均被当前面积支配 |
| 三种类别原地排序 | 荷兰国旗 | 从未知区换入的值要重查 |
| 两侧最高边界决定水位 | 前后缀极值 → 双指针 | 较小极值一侧已经可以结算 |
| 连续匹配且有重复前缀 | KMP | 失配后只保留合法的相等前后缀 |
三个易混对照
| 对照 | 关键区别 |
|---|---|
| 392 子序列 / 28 子串 | 子序列允许跳跃；子串必须连续，失配需重试或回退模式 |
| 27 移除元素 / 283 移动零 | 27 返回 k，尾部任意；283 返回 None，尾部必须零，非零保序 |
| 11 最大容器 / 42 接雨水 | 11 求一对边界的最大面积；42 求所有柱顶水量总和并扣除柱体 |
5 阶段计划与间隔复习
| 安排 | 任务 | 闭卷自测 |
|---|---|---|
| Day 1 · 45–60 分钟 | 344、125；基础与模板 A | 相遇条件、连续标点、数字保留 |
| Day 2 · 60–90 分钟 | 1768、392、88；模板 B | 任一输入先结束；m=0/n=0；逆向合并证明 |
| Day 3 · 60–90 分钟 | 27、26、283；模板 C | 有效前缀不变量；返回 k 与返回 None |
| Day 4 · 90–120 分钟 | 11、15；从枚举到排除 | 短板证明；[0,0,0,0] 的三层去重 |
| Day 5 · 120–150 分钟，可拆两天 | 75、42、28；模板 D/E | 未知区、雨水结算、独立构建 KMP 前缀表 |
| 首次学习后 +1 / +3 / +7 天 | 闭卷重做错误题与证明薄弱题 | 先写不变量，再写代码，最后用最小反例核对 |
若仍需看答案才能解释移动规则，暂不标记掌握，记录失败用例并回到同模板基础题。建议闭卷重写 27、88、11、15、75、42，将 28 的 KMP 作为进阶复述题。
掌握程度自测
题目勾选表示能独立实现；自测检查跨题迁移能力，单独保存，不会自动计入题目进度。
闭卷纠错
两个嵌套循环，所以一定是 O(n²)？
应计算指针总移动次数。回文跳过标点的两指针不回退，总 O(n)；三数之和每个锚点重扫后缀，才是 O(n²)。
颜色分类换到右端后，current 也应前进？
反例 [1,2,0]：2 换回 0 后若跳过当前位置，会留下 [1,0,2]；未知元素必须重查。
Python 原地 sort，辅助空间必然 O(1)？
原地只表示结果写回原列表，内部仍可能使用 O(n) 缓冲。双指针扫描本身 O(1)，排序与答案输出须另计。
移除元素后应把 nums[k:] 全设为零？
第 27 题只要求前 k 位合法，尾部任意；第 283 题才要求尾部全零，且返回 None。
使用说明与来源
严格覆盖输入的 13 道题，没有替换题目。每题包含题意、完整可提交代码、关键解释、推演、复杂度、边界与易错点。各解法可单独复制提交，图解全部内联。
题号、标题、难度和题目语义已对照各卡片中的力扣官方原题。动态页面的访问可能受网络或登录状态影响；完整约束请查原题。解法没有声称已在线提交，采用本地边界、穷举与随机对照验证。
进度与主题保存在当前浏览器对此文件的存储中，不保证跨浏览器、隐私窗口或文件移动后共享；存储禁用时会提示，当前会话仍可使用。打印可调用浏览器打印或另存 PDF。
参考：本地 leetcode_binary_tree_study_guide.html 的目录布局、代码样式、进度与主题机制。内容按双指针的学习依赖重新编排。版本：2026-10-27。