附录A · 速查

⏱ 31 分钟 ｜ ⭐ 临场想不起来时翻这一页：不变量一句话、模板一小段、写错了长什么样

📌 这一页是查的，不是读的。每一条都指回本板块的某一章。

🎯 一句话

这一页不讲怎么想出来，只把已经想出来的东西排好。 正文八章负责让你懂，这一页负责让你在白板前十秒钟内找回那句关键的不变量。

⚠️ 里面没有一行新代码 —— 全部从正文抄回，改了就对不上了。真要练，回到对应那一章把整段跑一遍。

🧭 一、先认出题型：数据形状 → 你真正要解决的问题

⭐ 00 章那条判据是这一页的骨架：一题先翻译成数据形状 + 一个变化动作 + 一个不变量，代码才会自己长出来。

📋 「我现在卡在哪」→ 直接跳哪一章：

🧩 二、⭐ 不变量卡：每题一句，忘了就看这一句

⭐ 这是全页最该扫的一节。 每一条都是正文里那句「循环里始终为真的事」。

🧯 三、⭐ 写错了长什么样：症状 → 它到底在说什么

用法：跑出错误答案或异常之后，在这一节找你看到的那句话。 ⚠️ 这类题最难的地方是多数错误不报异常，只是答案不对 —— 所以下面前半截是「症状」，后半截才是异常。

链表反转后只剩一两个节点，或者结果里出现 None

⭐ 先写了 cur.next = prev，再回头去找原来的 cur.next。 那时后路已经被覆盖，尚未处理的整个后缀就再也找不到了。 → 顺序永远是：nxt = cur.next 先保住后路 → cur.next = prev 再掉头 → 两队伍一起向前。见 01 章题 1。

合并链表时要写「第一个节点」的特殊分支，越写越乱

→ 用 dummy 假头。⭐ 它存在的唯一理由：让第一个节点和后面的节点一样接，不必写「第一次特殊处理」。见 01 章题 2。

💀 树的路径题：答案条数对，但内容全是空列表

⭐ answer.append(path) 写成了没有 [:] 的版本。 所有答案都指向同一个还会继续变化的列表，回溯弹完之后它们一起变空。 → 存答案必须 answer.append(path[:])。见 02 章题 3。

树的路径题：右子树的答案里混进了左边的节点

离开一个节点时没有 path.pop()。同一个 path 被左右子树共用，不复原现场，右子树会带着一段不属于它的旧路径继续走。见 02 章题 3。

滑动窗口最大值：窗口滑出去了，答案还是旧的那个最大值

⭐ 队列里存的是值而不是下标。 存下标不是细节 —— 只有知道下标，才判断得出队首是否已经离开窗口（queue[0] <= right - k）。见 03 章题 3。

IndexError: queue is empty（两个栈实现队列）

倒完 inbox 之后 outbox 仍然是空的 —— 队列本来就没有元素。⭐ 注意倒的时机：只有 outbox 空了才整批倒，中途倒会把顺序搅乱。见 03 章题 1。

二分：数组里没有目标时结果不对，或者目标比所有元素都大时越界

⭐ 右边界写成了 len(nums) - 1。 lower_bound 用的是半开区间 [left, right)，right = len(nums) 才表达得出「目标比所有元素都大」时的插入位置，也让空数组和边界判断统一。见 04 章题 1。

ValueError: k out of range（最小的 k 个数）

k 不在 0 <= k <= len(nums) 里。⚠️ 这是故意加的边界检查，不是 bug —— 面试里被追问边界时，它就是你的答案。见 04 章题 3。

最大子数组和：只维护了一个变量，答案偏小

⭐ 只记全局最大和，丢掉了「以当前点结尾」的那个状态。 下一轮需要知道前缀能不能接上，而全局最大和可能结束在很早的位置，不能直接接。见 05 章题 1。

递归的正则匹配跑得非常慢

同一批子问题被反复算。⭐ 看见「很多子问题重复算」先考虑记忆化，它就是从递归过渡到动态规划的桥。见 05 章题 3。

矩阵路径：某条真实存在的路径找不到

⭐ 走完一个分支后没把 board[r][c] 恢复回去。 这个格子只是当前分支不能再用；别的起点或兄弟分支仍然应该可以用它。见 06 章题 1。

排列结果里有重复项

同一层里同一个字符被试了不止一次。→ 每层用一个 used 集合，同一层相同字符只尝试一次。见 06 章题 3。

螺旋打印：单行或单列的矩阵，某些元素被打印了两次

⭐ 走下边和左边之前少了那两次边界判断。 只有一行时上边已经把元素拿完了，只有一列时右边已经拿完了。见 07 章题 3。

二进制加法在负数上死循环 / 结果离谱

⚠️ add_without_plus 那段对非负整数最直观。 Python 的负数是无限位语义，进位可以一直左移下去。面试若要求处理负数，要先约定 32 位掩码。见 07 章题 2。 ⭐ 反面在 NumPy · 08 整数 dtype 的真相：一进 NumPy 整数就是定宽的，越界不报错、直接回绕，而且没有任何信号。

atoi：'words and 9' 返回了 9

⚠️ 你在「读到非法字符」之后还继续找数字了。⭐ 四个阶段是顺序的，任何一步不符合规则就停止，不是「尽量猜」。正确结果是 0。见 08 章题 1。

最长无重复子串：结果比正确答案小

左边界回退了。⭐ 右边界已经向右扩展；回退左边界只会把已知会冲突的字符重新放回窗口，既无帮助又会重复计算。条件要写成 last_seen[char] >= left。见 08 章题 2。

📦 四、这套题用到的标准库，一张表

⭐ 本板块只用了三个 collections / heapq 的东西，每个都对应一个明确的需求：

⚠️ 面试若要求手写「最小的 k 个数」，用大小为 k 的最大堆；但先把「只维护 k 个候选」这个思想弄懂，容器是次要的。 ⭐ deque 为什么在这些题里非它不可（list.insert(0, x) 是 O(n)、deque.appendleft 是 O(1)，实跑差 299～1005 倍），在 Python 会咬你的地方 · 09 容器、哈希与顺序。

🧪 五、每题的小闭环，和「做完了」的标准

⭐ 00 章定的四步，卡住时按它走：

1. 先用 3–6 个元素手画一次，不急着敲代码。
2. 用一句话写下循环里「始终为真」的事 —— 那就是不变量（第二节整节都是它）。
3. 把代码复制运行，至少换一个边界输入：空、一个元素、重复、极值。
4. 卡 10 分钟时先看「关键不变量」，不要直接滚到完整代码。

⭐ 完成标准不是 AC 过一次，而是第二天遮住代码后还能说出：指针 / 下标各代表谁、每轮为什么不会漏。

📋 每类题该补的边界输入：

🔗 这一页连到哪里

⭐ 这一页最该带走的一句：题目换名字没关系；数据形状和不变量没换，解法就还在。

下一节 👉 回到板块索引