编程面试的核心套路（模式化刷题）
结论先行：编程面试题目千变万化，底层模式就十几个。会识别"这题属于哪个模式"，比盲刷题量更重要。目标是看到题面能在 30 秒内报出候选模式和数据结构。
相关阅读：动态规划系统指南、最长递增子序列、系统设计面试框架、技术面试英语。
1. 高频模式速查表
| 模式 | 识别信号 | 典型题 | 复杂度 |
|---|---|---|---|
| 双指针 | 有序数组、找配对/去重 | 两数之和 II、三数之和 | O(n) |
| 滑动窗口 | 连续子数组/子串、最长/最短 | 无重复最长子串 | O(n) |
| 快慢指针 | 链表环、找中点 | 环形链表、找中位节点 | O(n) |
| 二分查找 | 有序、"最小的满足…" | 搜索旋转数组、峰值 | O(log n) |
| BFS | 最短路径、层序 | 岛屿最短路、层遍历 | O(V+E) |
| DFS / 回溯 | 排列组合、所有方案 | 全排列、子集、N 皇后 | 指数级 |
| 堆 / Top-K | "第 K 大/小"、合并有序流 | 前 K 高频、合并 K 链表 | O(n log k) |
| 哈希表 | O(1) 查存在/计数 | 两数之和、字母异位词 | O(n) |
| 前缀和 / 差分 | 区间求和、子数组和 | 和为 K 的子数组 | O(n) |
| 单调栈/队列 | "下一个更大/更小" | 每日温度、柱状图最大矩形 | O(n) |
| 并查集 | 连通性、分组 | 朋友圈、冗余连接 | ~O(nα) |
| 拓扑排序 | 依赖顺序、有向无环 | 课程表 | O(V+E) |
| 区间 | 合并/重叠区间 | 合并区间、会议室 | O(n log n) |
| 动态规划 | 最优子结构、重叠子问题 | 背包、编辑距离、LIS | 视题而定 |
| Trie | 前缀匹配、字典 | 单词搜索、自动补全 | O(L) |
2. 怎么"识别模式"
拿到题先问三件事：
- 输入结构：有序吗？树/图/链表/矩阵？
- 要什么：最短/最长/计数/所有方案/存在性？
- 约束规模：n 多大 → 反推目标复杂度（n≤20 可指数；n≤10^3 可 O(n²)；n≥10^5 需 O(n log n) 以内）。
信号→模式的常见映射：
- "连续子数组/子串 + 最长/最短" → 滑动窗口。
- "有序 + 找某个临界点" → 二分。
- "所有排列/组合/子集" → 回溯。
- "第 K 个" → 堆 或 快速选择。
- "下一个更大" → 单调栈。
- "依赖/前置条件" → 拓扑排序。
- "最优 + 可拆成子问题" → DP（见 DP 指南）。
3. 两个模板
滑动窗口（变长）
l = 0; 维护窗口状态
for r in range(n):
加入 nums[r]
while 窗口不合法:
移除 nums[l]; l += 1
更新答案(r - l + 1)回溯
def backtrack(path, choices):
if 满足终止: 记录 path; return
for c in choices:
做选择 c
backtrack(path+[c], 更新后的 choices)
撤销选择 c4. 学习路径（效率优先）
- 先把上表 15 个模式各吃透 3–5 题，手写模板到肌肉记忆。
- 每题练"识别→报模式→说复杂度→再写码"的口头流程（面试要边说边写，见 技术面试英语）。
- 用间隔重复复盘错题，按模式归类而非按题号。
- 后期做限时模拟（35–40 分钟一题含沟通）。
5. 常见陷阱
- 盲目刷题量，不做模式归纳 → 换个包装就不会。
- 不先讲思路直接写码 → 面试沟通分丢光。
- 不报复杂度、不说边界（空、单元素、越界）。
- 只求 AC 不复盘更优解。
小结
把面试算法当模式匹配问题：吃透十几个套路、练熟模板、练"边说边写"，比刷题海高效得多。识别对模式，题目就解决了一大半。