算法题分类学习大纲
学习原则
- 每类先做 3
5 道暴力解法，再做 35 道优化
- 先看题解搞清楚”这题属于哪类模式”，再刷同类题
- 不以题量为目标，以”看到新题能判断属于哪类”为目标
一、线性结构（数组/链表/字符串）
1. 双指针
通常出现在有序数组或链表上，两个指针从两端往中间走，或者一快一慢。
| 子类 | 代表题 |
|---|
| 左右指针（对撞） | 两数之和 II、盛最多水的容器 |
| 快慢指针 | 环形链表检测、链表中点 |
| 三指针（荷兰国旗） | 颜色分类 |
2. 滑动窗口
找子串或子数组，问题描述通常是”最长的满足某条件的连续区间”。
| 关键技巧 | 代表题 |
|---|
| 右扩左缩 | 无重复字符的最长子串 |
| 固定窗口 | 大小为 K 的子数组最大和 |
| 计数窗口 | 最小覆盖子串 |
3. 原地修改
要求 O(1) 空间，把数组索引本身当成工具来用。
| 关键技巧 | 代表题 |
|---|
| 循环置换（cyclic sort） | 缺失的第一个正整数 |
| 正负号标记 | 数组中的消失数字 |
| 数组翻转/旋转 | 轮转数组 |
二、查找与排序
4. 哈希表 / Set
需要快速”查重”或”按条件分组”时用。
| 关键技巧 | 代表题 |
|---|
| 计数 | 多数元素 |
| 两数之和 | Two Sum |
| 分组 | 字母异位词分组 |
5. 二分查找
数据有序，或问题本身隐含了有序性质，在答案范围内二分搜索。
| 关键技巧 | 代表题 |
|---|
| 值二分 | 搜索插入位置 |
| 答案二分 | 分割数组的最大值 |
| 旋转数组二分 | 搜索旋转排序数组 |
6. 堆
动态找第 K 大/小，或需要反复取最大/最小值。
| 关键技巧 | 代表题 |
|---|
| Top K | 前 K 个高频元素 |
| 多路归并 | 合并 K 个升序链表 |
| 中位数 | 数据流的中位数 |
三、树与图
7. 二叉树遍历
| 关键技巧 | 代表题 |
|---|
| 前中后序遍历（递归） | 二叉树的中序遍历 |
| 层序遍历（BFS） | 二叉树的层序遍历 |
| Morris 遍历（O(1) 空间） | 进阶：用常数空间遍历 |
8. 递归 / 分治
大问题能拆成结构相同的小问题，子结果能组合成最终答案。
| 关键技巧 | 代表题 |
|---|
| 自顶向下 | 二叉树的最大深度 |
| 自底向上 | 平衡二叉树判断 |
| 路径问题 | 路径总和 |
9. 图
节点之间有多条关联，可能有环，不是树。
| 关键技巧 | 代表题 |
|---|
| DFS | 岛屿数量（二维网格也是图） |
| BFS | 最短路径（无权图） |
| 拓扑排序 | 课程表 |
| 并查集 | 省份数量 |
四、动态规划
动态规划是面试里最难的一类，但它的模式其实很固定。一句话概括：当前状态能从之前的状态推出来。
10. 一维 DP
| 子类 | 代表题 |
|---|
| 斐波那契型 | 爬楼梯 |
| 最大子数组和 | Kadane 算法 |
| 打家劫舍型 | 不能相邻 |
11. 二维 DP
| 子类 | 代表题 |
|---|
| 网格路径 | 不同路径 |
| 字符串编辑距离 | 编辑距离 |
| 背包问题 | 0-1 背包、完全背包 |
12. 经典 DP 模式
| 模式 | 关键词 |
|---|
| 选或不选 | 背包系列 |
| 区间 DP | ”从 i 到 j” |
| 状态机 DP | 买卖股票系列 |
五、回溯与穷举
13. 回溯
题目要求列举”所有可能的组合/排列”，搜索空间像一棵树。
| 关键技巧 | 代表题 |
|---|
| 组合 | 组合总和 |
| 排列 | 全排列 |
| 子集 | 子集 |
| 剪枝优化 | N 皇后 |
六、杂项（面试低频，竞赛会考）
| 类别 | 应用场景 |
|---|
| 前缀和 | 区间和快速查询 |
| 差分数组 | 区间频繁修改 |
| 单调栈 | 下一个更大元素 |
| Trie（前缀树） | 单词搜索、自动补全 |
| 贪心 | 局部最优 = 全局最优 |
| 位运算 | 只出现一次的数字 |
| 数学 | 质数、最大公约数、快速幂 |
推荐学习顺序
第一阶段（建立信心）
├── 哈希表（Two Sum 等）
├── 双指针
├── 滑动窗口
└── 二叉树遍历（递归）
第二阶段（核心能力）
├── 二分查找
├── 堆
├── 回溯
└── 一维 DP
第三阶段（进阶突破）
├── 图（BFS/DFS/拓扑排序）
├── 二维 DP
├── 并查集
└── 单调栈
第四阶段（按需补充）
├── 贪心
├── Trie
├── 位运算
└── 高级数据结构（线段树等）
一题多练
同一道题用不同解法各做一遍，比连刷好几道新题管用：
| 题 | 解法 1 | 解法 2 | 解法 3 |
|---|
| 两数之和 | 暴力 O(n²) | 哈希 O(n) | 双指针 O(nlogn) |
| 数组中的第 K 大元素 | 排序 O(nlogn) | 堆 O(nlogk) | 快排分区 O(n) |
| 最长回文子串 | 暴力 O(n³) | 中心扩散 O(n²) | DP O(n²) |
每道题练的不是数学推导，是模式识别。你不会一道题，不是你不行，是你还没见过这个模式。做多了会发现，算法题来来回回就那么十几类，新题基本是旧模式的排列组合。