算法刷题问题总结
刷题的价值不在 AC 那一下，在于把「下次见到它的 cousins 时的第一反应」存进脑子。题目是无限的，特征是有限的——总结题目没意义，总结特征反应才有复利。
这篇是站内算法笔记的总入口：先讲刷题方法，再给一张「特征 → 解法」的速查地图，最后沉淀一些跨题型的结论卡和易错点。
1. 刷题不是背题，是存「特征反应」
一道题做完，真正值得留下的只有三个问题：
- 什么结构性质让它可解？ 有序？无环？子问题重叠？——这是解法的根。
- 不变量是什么？ 指针/状态的每一步移动，凭什么敢淘汰候选。这个概念在 双指针：从「背模板」到「懂不变量」 里展开过，它适用于所有算法，不只是双指针。
- 边界在哪？ 空输入、单元素、全相同、目标在端点——错题九成死在这里。
一个自测标准
合上编辑器，能不能用一句话说清「这题考的特征 + 对应的反应」？ 说得出来这题就没白刷，说不出来就是背了一道题，明天就忘。
2. 题型地图：看到特征，往哪想
| 输入特征 | 首选方向 | 站内详解 |
|---|---|---|
| 有序数组 + 找配对/目标值 | 相向双指针、二分 | 双指针、二分查找 |
| 连续子区间 + 最值/计数 | 滑动窗口 | 滑动窗口 |
| 所有可能方案（排列/组合/子集） | 回溯 | 递归与回溯、组合问题 |
| 最优值 + 子问题重叠 | 动态规划 | 动态规划 |
| 层级遍历 / 无权图最短路 | BFS | 广度优先搜索 |
| 连通性 / 一条路走到底 | DFS | 深度优先搜索 |
| 链表位置问题（环/中点/倒数） | 快慢指针 | 双指针 |
| 状态压缩 / 成对消除 | 位运算 | 位运算、异或 |
| Top K / 流式取最值 | 堆 | 堆排序 |
| 大量定时/过期任务 | 时间轮 | 时间轮算法 |
| 数值构造 + 回文判定 | 双指针构造 | 回文十进制数 |
这张表是索引不是答案：特征命中后，去对应的详解里补「为什么」。
3. 问题汇总（知识卡）
结论卡，不是教科书——每张卡只留能直接用的东西。
树：二叉搜索树
左子树所有节点小于根，右子树所有节点大于根，左右子树各自递归。它同时拿到链表的插入删除效率和数组的查找效率，代价是**平衡性没有保证**——顺序插入退化成链表，操作全变 O(n)。红黑树、AVL 的存在就是为了修这个坑。
堆：数组里的完全二叉树
用数组下标模拟树：父节点 (i-1)/2，孩子 2i+1 和 2i+2，零指针开销。插入时在尾部上浮、删除堆顶时把尾元素下沉，都是 O(log n)；自底向上建堆是 O(n)，比逐个插入的 O(n log n) 划算。堆只承诺堆顶最优——找第 K 大就把堆规模压在 K。
链表：两个经典结论
判环用快慢指针，正确性是相对速度为 1、距离每轮缩短 1，必然相遇（详见 双指针）。倒数第 N 个节点用「预置距离」：快指针先走 n+1 步，之后同步移动，距离恒定直到快指针触底。
复杂度速查
| 结构 | 查找 | 插入 | 删除 |
|---|---|---|---|
| 有序数组（二分） | O(log n) | O(n) | O(n) |
| 链表 | O(n) | O(1)，需已知位置 | O(1)，需已知前驱 |
| 平衡 BST | O(log n) | O(log n) | O(log n) |
| 哈希表 | O(1) 均摊 | O(1) 均摊 | O(1) 均摊 |
| 堆 | O(1) 看堆顶 | O(log n) | O(log n) 删堆顶 |
没有银弹：哈希快但无序，数组查找快但插入贵，堆只管最值。选结构 = 对着操作频率做取舍。
4. 跨题型易错点
- ⚠️ 终止条件靠画图。空、单元素、双元素三个最小 case 纸上走一遍，比背十个模板可靠。
- ⚠️ 链表删除必上哨兵。
dummy节点把「删头」从特例变成普通 case。 - ⚠️ 整数溢出。求和、平方、阶乘先想上界：
n ≤ 10^5时平方和就可能爆 int32，该上int64就上。 - ⚠️ 「全部相同」是隐藏杀手。二分的
<=与<、去重的跳过逻辑，在这个 case 上最容易翻车。 - ✅ 提交前过一遍三个问题：结构性质对不对、不变量还成立吗、边界覆盖了吗。
小结
刷题的复利公式：每题一张卡（特征 + 反应 + 边界），卡片连成地图。题是做不完的，但特征空间有限——把有限的东西装进脑子，无限的题目就变成了查表。
最后更新：2026-09-14