套路速查
十七类题,各自的那几行心法
摘自每个分类源文件开头的总结。做完一类题再回来读一遍,比单题刷十遍更管用。
哈希
Hash
把「查找另一个值」从重复扫描变成常数时间查询。
【本类题的通用思路】
哈希表的本质是「用
O(n) 空间,把一次线性扫描变成 O(1) 查询」。
凡是看到「是否存在配对 / 出现过几次 / 属于同一组」,先想哈希。
三个高频坑:
1) 边查边存 —— 避免同一个元素和自己配对(Q1 的 [3,3])
2) unordered_map 的 key 可以是 string / 数组签名,但不能直接用 vector<int>
3) 判断「连续」时要先去重,否则 1,1,1,2 会算错长度(Q128)双指针
Two Pointers
利用有序性或两端信息,让两个指针只朝答案收缩。
【套路】
1) 对撞指针:有序 / 能判断「往哪边走更优」时,l 与 r 相向而行,
O(n)。
2) 快慢指针:原地搬运元素(去重、移动零)或找环。
3) 双指针去重:排序后在同一层跳过重复值。以 Q15 为例:
外层 if (i > 0 && nums[i] == nums[i - 1]) continue;
内层 while (l < r && nums[l] == nums[l + 1]) ++l;
这是所有「返回所有不重复组合」题的通用手法。滑动窗口
Sliding Window
维护一个始终满足约束的连续区间,避免重复计算。
【窗口三问】写滑动窗口前先答清楚:
1. 右边界进来时,窗口被破坏的条件是什么?(更新状态)
2. 什么时候必须收缩左边界?(while 条件)
3. 答案在收缩前更新还是收缩后更新?(取值时机)
定长窗口(Q438)用 if 每步弹出一个;变长窗口有两种写法:
while 逐步缩到合法(Q76),或直接把 left 跳到破坏点之后(Q3 的「跳跃式」)。
子串 / 前缀和
Substring & Prefix Sum
用前缀信息或窗口把连续区间问题拆成可复用的状态。
【两个新工具】
1) 前缀和 + 哈希:区间和 = pre[r] - pre[l-1]。要「和为 K 的子数组个数」,
就是对每个 r 数有多少个 l 满足 pre[l] = pre[r] - K —— 计数查表
O(n)。
注意:有负数时滑动窗口失效(窗口和不单调),只能用前缀和。
2) 单调队列 / 单调栈:维护一个「候选最优」的递减(递增)序列,
队首始终是当前窗口最值 —— 每个元素进出队各一次,均摊 O(1)。普通数组
Array
围绕下标、原地状态和局部不变量组织一次或有限次扫描。
【本组的思维母题】
· 一维 DP 入门:Q53 的「以 i 结尾的最大和」是最大子数组问题的原型。
· 排序 + 扫描:区间题几乎都是「按左端点排序后线性合并」。
· 原地
O(1) 空间:数组下标本身就是哈希表(Q41 索引标记、Q189 三次反转)。矩阵
Matrix
把二维坐标关系转成有边界的行列遍历或原地标记。
【套路】
1) 边界收缩法:用 top/bottom/left/right 四个变量描述尚未走完的矩形,
每走完一条边就收缩一次 —— 螺旋类题目的万能模板,比「方向数组 + 转向」少想很多。
2) 借用第一行/第一列当标记位,把
O(m+n) 额外空间压成 O(1);
但要单独记住「第一行/第一列本身是否要置零」,否则会互相污染。
3) 阶梯查找:矩阵行列双有序时,从右上角出发,比目标小就下移、大就左移,
O(m+n)。左下角同理。绝不能用普通二分(整体不是单调的)。链表
Linked List
指针不能丢:先保存 next,再改变连接关系。
【链表通用心法】
1) 哨兵结点 dummy:凡是「头结点可能被删/被换」的题,一律从 dummy 出发,
最后 return dummy.next。能消掉 90% 的头结点特判。
2) 快慢指针三件套:找中点、找倒数第 k、判环。
3) 反转是基本功:prev / cur / nxt 三个指针,先存 nxt 再改链。
4) 判环的数学:设 head→入口 = a,入口→相遇点 = b,相遇点→入口 = c,环长 L = b + c。
相遇时 slow 走了 a+b,fast 走了 a+b+kL,而 fast = 2·slow ⇒ a+b 是 L 的整数倍,
所以 a ≡ c (mod L) —— 一个指针回到 head、两个各走 1 步,必在入口相遇(推导见 Q142)。
5) 测试里造过环的链表不好统一释放,本文件部分用例故意让进程退出时回收。
- 160相交链表先对齐起点:长链表多走差值步简单
- 206反转链表三指针迭代反转 / 递归版简单
- 234回文链表快慢找中 + 反转后半 + 逐一比对简单
- 21合并两个有序链表哨兵头结点 + 逐一接较小者简单
- 2两数相加逐位相加,哨兵结点简化尾插中等
- 19删除链表的倒数第 N 个结点快指针先走 n 步,再同步走到尾部中等
- 24两两交换链表中的节点dummy + 每次交换相邻一对中等
- 25K 个一组翻转链表数够 k 个就整组反转,再串接困难
- 138随机链表的复制原地把 next 指向克隆结点,再拆两条链中等
- 148排序链表归并:快慢找中 + 递归 + 合并两链中等
- 23合并 K 个升序链表小顶堆按值合并 k 路 / 分治困难
- 146LRU 缓存哈希表 + 双向链表,get/put 都 O(1)中等
- 141环形链表Floyd 快慢指针,相遇即有环简单
- 142环形链表 IIa=(k-1)(b+c)+c → 从头与从相遇点同速中等
二叉树
Binary Tree
每个节点都问同一个递归问题,再把左右子树答案合并。
【递归的两种姿势 —— 想清楚这个,二叉树题就通了】
A. 「自顶向下」:参数里带上下文(路径和、上下界、前缀和表),
像前序遍历,进入结点时先处理携带的信息。例:Q113 路径总和、Q437。
B. 「自底向上」:返回值里带信息(高度、链贡献、最大贡献),
像后序遍历,用左右子树的返回值算出本结点的答案。例:Q104、Q543、Q124。
另外两条主线:
· BFS + 分层 for 循环 = 所有「按层」问题(Q102 层序、Q199 右视图、Q103 锯齿)。
· BST 的中序遍历严格递增 —— Q98 / Q230 / Q538 / Q700 都靠这一句话。
- 94二叉树的中序遍历迭代栈 / Morris;递归就是左根右简单
- 104二叉树的最大深度递归 max(左高,右高)+1简单
- 226翻转二叉树递归交换左右孩子简单
- 101对称二叉树递归比较(左左,右右)与(左右,右左)简单
- 543二叉树的直径后序:过每个结点的直径=左高+右高简单
- 102二叉树的层序遍历BFS 按层出队,用 size 定层宽中等
- 108将有序数组转换为二叉搜索树取中点做根,左右两半递归简单
- 98验证二叉搜索树上下界区间收缩(只比父子会错)中等
- 230二叉搜索树中第 K 小的元素中序遍历第 k 个 / BST 迭代器中等
- 199二叉树的右视图BFS 每层最后一个结点中等
- 114二叉树展开为链表先序展开:左子树右端接右子树中等
- 105从前序与中序遍历序列构造二叉树前序定根 + 中序切两半(下标哈希加速)中等
- 437路径总和 III树上前缀和 + 哈希(Q560 的树版)中等
- 236二叉树的最近公共祖先后序:两侧都有即答案,否则返回非空那侧中等
- 124二叉树中的最大路径和DFS 只返回「单边贡献」,答案全局取 max困难
图论
Graph
把「连通、依赖、扩散」转成 DFS、BFS 或拓扑序。
【网格就是图】
m×n 的网格里每个格子是结点,上下左右(有时含对角)是边。于是:
· 求连通块个数 -> DFS/BFS 把访问过的「沉掉」(Q200)
· 多源最短步数 -> 把所有源点同时入队做 BFS(Q994、Q127、Q130)
· 判有没有环 -> 拓扑排序:能出完 n 个点就无环(Q207)
注意 DFS 递归深度 = 连通块大小,300×300 全 1 的网格会到 9 万层,
真实工程里应改 BFS 或手写栈;面试口头说明这点即可。
回溯
Backtracking
选择、递归、撤销选择,枚举搜索树并尽早剪枝。
【回溯 = 在决策树上做 DFS】
模板永远是这三行:
选择 -> 递归下一层 -> 撤销选择
写之前先回答三个问题:
1. 决策树的「一层」是什么?(选一个元素 / 放一行皇后 / 加一个括号)
2. 何时算到达路径终点、可以收集答案?(长度够了 / 和等于 target / 无更多可选)
3. 剪枝条件是什么?(越界、重复、数量不合法、和已经超过 target)
start 参数的三种形态,正是「排列 / 组合 / 子集」的区别:
· 组合、子集:下一层传 i+1(不回头,天然无序,避免 {1,2} 与 {2,1} 重复)
· 可重复使用的组合(Q39):下一层传 i(允许再选自己)
· 排列:不用 start,每层从 0 扫,靠 used[] 排除已在路径里的元素
二分查找
Binary Search
答案具有单调性,就能每次排除一半候选。
【把二分写成两个模板,别每次现推】
A. 精确查找(找 target):while (lo <= hi),命中即返回,最后 lo 是插入位置。
B. 边界查找(找「第一个 >= x」,即 lower_bound):while (lo < hi),
条件成立就 hi = mid,否则 lo = mid + 1;返回 lo。
三条铁律:
1. mid = lo + (hi - lo) / 2 —— 防 (lo+hi) 溢出,这是面试硬要求。
2. 想清楚区间语义:[lo, hi] 闭区间配 hi = mid - 1;[lo, hi) 半开区间配 hi = mid。
混用是死循环 / 越界的根源。
3. 二分的本质不是「数组有序」,而是「存在一个 predicate,使序列呈 FFFTTT」。
所以旋转数组(Q33/Q153)、答案二分(Q875 koko 吃香蕉)都能二分值域。
实盘建议:优先用 std::lower_bound / upper_bound,少写错;但必须会手写。
栈
Stack
栈保存「最近还没解决」的状态,适合嵌套和单调关系。
【单调栈:一类题一个模板】
求「左边/右边第一个更大/更小的元素」,全都用单调栈:
for each x:
while (栈顶破坏了单调性) { 弹出并结算 }
此刻栈顶就是 x 要找的那个「第一个更大/更小者」
x 入栈
栈内维持什么,取决于你要找什么:
· 找「右边第一个更大」-> 栈递减(Q739 每日温度)
· 找「左右第一个更小」-> 栈递增(Q84 柱状图)
为什么是
O(n):每个下标最多入栈一次、出栈一次。
另一个大类:括号匹配 / 嵌套结构 -> 普通栈(Q20、Q394、Q150、Q224)。
顺带一提:Q42 接雨水也能用单调栈(按「凹槽」逐层结算),和双指针法互为验证。堆
Heap / Priority Queue
只维护当前最需要的少量候选,不必全排序。
【三件套】
1. 「第 K / 前 K」问题 -> 维护大小为 K 的堆,比全排序
O(n log n) 优:
· 求第 K 大:用小顶堆装 K 个最大的(堆顶是这 K 个里最小的 = 答案)
· 求前 K 高频:小顶堆按频次淘汰,或桶排序做到 O(n)
记忆口诀:第 K 大用小顶堆,第 K 小用大顶堆(堆顶是「守门员」)。
2. 「流式 / 动态求中位数、第 K 小」-> 对顶堆:
大顶堆装较小的一半,小顶堆装较大的一半,保持两堆 size 差 <= 1,
中位数就在两个堆顶之间(Q295、Q480、Q502 都能套)。
3. C++ 的 priority_queue 默认是「大顶堆」!
小顶堆要显式写:priority_queue<int, vector<int>, greater<int>>
自定义比较时注意:comp(a,b)==true 表示 a 的优先级低于 b(跟 sort 相反方向)。贪心
Greedy
每一步做可证明的局部最优,把全局问题逐步缩小。
【贪心能不能用,看两件事】
1. 贪心选择性质:局部最优选择不会影响后续的可解性(能证明「exchange argument」:
把任一最优解的第一步换成我的贪心选择,解不会变差)。
2. 最优子结构:剩下的子问题的最优解 + 我的选择 = 全局最优。
不满足就必须上 DP。经典反例:零钱兑换用「每次取最大面额」是错的
(coins=[1,3,4], amount=6:贪心得 4+1+1 三张,最优是 3+3 两张 —— 见 Q322)。
跳跃类题目的统一视角:把「能到达的最远处」当成贪心状态,
能到 i 才能从 i 出发(Q55 判可达、Q45 数步数、Q1306/Q1345 同理)。
动态规划(一维)
Dynamic Programming
把大问题写成状态,让每个状态只算一次。
【写 DP 的固定五问】
1. 状态怎么定义?(dp[i] 表示「以 i 结尾」还是「前 i 个」?这一步错了后面全错)
2. 转移方程是什么?(dp[i] 由哪些更小的状态算出 —— 就是「最后一步有几种走法」)
3. 边界/初始化?(dp[0] 表示空;「凑不出」一般设成 +INF/-1 之类的哨兵)
4. 遍历顺序?(依赖前一个 -> 正序;0-1 背包用一维时必须逆序,见 Q416)
5. 返回值在哪?(不一定在 dp[n],Q300/Q152 要取 max(dp[i]))
【三类一维 DP 的识别信号】
· 线性递推(爬楼梯、打家劫舍):只依赖前 1~2 项 -> 两个变量滚动,空间
O(1)。
· 背包(零钱、完全平方、等和子集):dp[容量],
完全背包(可重复选)内层正序;0-1 背包(每个只能用一次)内层逆序。
· 「以 i 结尾」型(LIS、最大子数组积):dp[i] 只表示「必须选 i」的最优,
答案要全局取 max —— 这类最容易只返回 dp[n-1] 而写错。- 70爬楼梯dp[i]=dp[i-1]+dp[i-2],滚动两变量简单
- 118杨辉三角tri[i][j]=上一行相邻两数之和简单
- 198打家劫舍偷/不偷:max(prev1, prev2+x)中等
- 279完全平方数完全背包求最少平方数个数中等
- 322零钱兑换完全背包求最少硬币(贪心必错)中等
- 139单词拆分dp[i]=前 i 个能否拆成词典词(布尔背包)中等
- 300最长递增子序列tails[k]=长度 k 的最小结尾 + lower_bound中等
- 152乘积最大子数组同时维护最大积与最小积,遇负交换中等
- 416分割等和子集0-1 背包判定,一维数组必须逆序中等
- 32最长有效括号栈底存最后一个破坏位 / 也可区间 DP困难
多维动态规划
2D DP
明确 dp[i][j] 的含义,再按依赖方向填表。
【什么时候开二维数组】
· 网格型:位置由 (i,j) 决定 -> dp[i][j](Q62/Q64/Q79 计数版)。
· 双串型:状态是「A 的前 i 个 vs B 的前 j 个」-> dp[i][j](LCS、编辑距离、
Q10 正则匹配、Q97 交错字符串)。这类题的通用写法就是三格转移:
dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
· 区间型:状态是「子串 s[i..j]」-> dp[i][j],枚举区间长度 + 断点 k
(Q5 回文判定、Q131/Q132 分割、Q312 戳气球)。遍历顺序必须
保证 dp[i+1][...] 先算:常见是 i 从大到小、j 从小到大,或按长度枚举。
【降维规则】当 dp[i][j] 只依赖第 i-1 行时,可以压成一行;
但如果同时还依赖「本行的 dp[i][j-1]」,压一维时要小心更新顺序
(从左往右扫正好利用了新值;需要 dp[i-1][j-1] 时要额外存一个变量)。
技巧
Techs
借助位运算、数学规律或原地映射压缩空间。
【五个必背技巧】
1. 位运算异或:a^a=0、a^0=a、满足交换律结合律
-> 「只出现一次」类题目的标准解(Q136);推广到「出现 3 次」见 Q137,
用「统计每一位上 1 的个数 mod 3」或两个掩码状态机。
2. 摩尔投票(Boyer-Moore):维护 candidate + count,相同 +1、不同 -1、归零换人。
原理:把「一对不同的元素」互相抵消,出现 > n/2 的元素一定有剩。
注意:它只保证「如果存在多数元素,则一定是这个 candidate」;
题目没保证存在时,必须再扫一遍验证(Q169 不需要,Q229 的 1/3 版本要)。
3. 荷兰国旗三向切分:p0 / i / p2 三个指针把数组切成 <1 / ==1 / >1 三段(即 0 | 1 | 2),一趟排完。
这就是快速排序的三路划分,也是「Dutch national flag problem」。
4. 下一个排列(Q31):从右往左找第一个下降位 -> 与右边「刚好比它大」的数交换 ->
反转后缀。C++ 有 std::next_permutation,但必须会手写(Q556/Q670 同款)。
5. 值域下标当链表用(Q287/Q41/Q442/Q645):数组元素落在 [1,n] 时,
nums[i] 天然构成 i -> nums[i] 的函数图,重复元素 => 图上一定有环 =>
用 Floyd 龟兔赛跑找环入口。另一路是「把 nums[x] 对应位置取负」当 visited。
两者都是
O(1) 额外空间,且都要求数组可(临时)修改或至少能构造慢指针。