ALGO PATTERNS · 刷题套路 / 模板速用
刷题套路速查
双指针、滑动窗口、二分边界、BFS/DFS、动态规划、回溯与贪心、前缀和差分——刷题最高频的 48 个解题套路与模板一张表收齐，随查随用。
48条套路
8大模块
∞持续更新
📖 速查表
点击展开各小节
🎯 双指针与滑动窗口
| 套路 | 要点 | 典型题 / 模板 |
|---|---|---|
| 对撞指针 | 有序数组首尾各一个指针相向移动，利用单调性一次遍历完成两数关系判定 | 两数之和 II、盛最多水的容器、三数之和、反转数组、回文串判断 |
| 快慢指针 | 同向移动、速度不同：判环与找中点是标准应用，相遇即有环 | 环形链表、环形链表 II（找入环口：头与相遇点同速前进再相遇）、链表中点、删除倒数第 N 个 面试高频 |
| 同向指针（原地操作） | 读写指针分离：写指针只在保留条件成立时前进，实现 O(1) 空间原地修改数组 | 移除元素、删除有序数组重复项、移动零、原地去重 |
| 滑窗口诀 | 「右扩左缩」：右指针扩窗探索，窗口不合法时左指针收缩，用哈希/计数器维护窗口状态，每元素进出各一次 O(n) | 无重复字符的最长子串、最小覆盖子串、长度最小的子数组 必背 |
| 滑窗模板 | 状态更新放在扩窗后，收缩放在扩窗后立即处理，答案在窗口合法时统计 | while (r < n) { 窗口加入 s[r] while (窗口不合法) 移出 s[l] ans = max(ans, r - l + 1) } |
| 定长滑窗 | 窗口大小固定 k：右进一元素、左出一元素同步进行，维护窗口内聚合值（和/最大值/计数） | 大小为 K 且平均值大于等于阈值的子数组、子数组最大平均值、定长串排列（含计数比较） |
| 单调队列优化滑窗 | 需快速取「滑动窗口最大/最小值」时，用单调递减队列存下标：队头即窗口最值 | 滑动窗口最大值、跳跃游戏 VI；队尾弹小、队头过期弹 进阶模板 |
🔍 二分查找
| 套路 | 要点 | 典型题 / 模板 |
|---|---|---|
| 标准二分模板 | 闭区间 [l, r]，循环条件 l <= r，命中即返回；前提是序列具有单调性（二段性） | while (l <= r) { mid = l + (r - l) / 2 if (a[mid] == t) return mid else if (a[mid] < t) l = mid + 1 else r = mid - 1 } |
| 防溢出写法 | (l + r) / 2 在大数组下可能整型溢出，统一改写为 l + (r - l) / 2 | 所有二分变体的默认习惯 细节分 |
| 找左边界 | 求第一个 ≥ target 的位置：命中不返回而是收缩右半，区间收敛到 l == r | while (l < r) { mid = (l + r) / 2 if (a[mid] >= t) r = mid else l = mid + 1 } |
| 找右边界 | 求最后一个 ≤ target 的位置：mid 需上取整防死循环，命中向右收缩 | mid = (l + r + 1) / 2 if (a[mid] <= t) l = mid else r = mid - 1 易混淆 |
| 二分答案 | 「最小值最大化 / 最大值最小化」：答案区间有单调性（可行→不可行连续分界），对答案本身二分 + 判定函数 check | 爱吃香蕉的珂珂、分割数组的最大值、运输问题、木材加工 面试高频 |
| 适用信号 | 题面出现「有序」「最小化最大值」「最大化最小值」「至少需要多少」，且可行性与某量值单调相关 | 旋转数组搜索（局部有序）、峰值元素、x 的平方根、旋转矩阵找数 |
| 常见坑 | 边界写混导致死循环或漏解：循环条件与开闭区间必须配套；找左/右边界时 mid 取整方向要相反 | while (l < r) 搭配 r = mid 不用 -1，搭配 l = mid 必须 mid 上取整 死循环高发 |
🌳 BFS 与 DFS
| 套路 | 要点 | 典型题 / 模板 |
|---|---|---|
| 层序 BFS 模板 | 队列 + visited：入队即标记防重复；按层处理时先记录当前队列长度再整层出队 | queue.offer(start); visited[start] = true while (!q.isEmpty()) { size = q.size() // 一层 for (i = 0..size) { cur = q.poll() for (next : 邻居) if (!visited[next]) { 标记; 入队 } } } |
| BFS 要点 | 无权图最短路径唯一解法；visited 必须在入队时标记而非出队时，否则同层重复入队导致超时 | 二叉树层序遍历、最短路径、01 矩阵、打开转盘锁 必背 |
| 岛屿类问题套路 | 网格遍历 + 感染式 DFS/BFS：遇到陆地计数并「淹没」（标记为 0/visited），避免重复统计 | 岛屿数量、岛屿最大面积、封闭岛屿、被围绕的区域、太平洋大西洋水流 面试高频 |
| 方向数组 | 网格四方向统一用偏移数组驱动，代码更短且不易漏方向 | dirs = {{1,0},{-1,0},{0,1},{0,-1}} for (d : dirs) { nx = x + d[0]; ny = y + d[1] if (在界内且未访问) dfs(nx, ny) } |
| 回溯三要素 | 路径（已做选择）、选择列表（还能做什么）、结束条件（路径满足要求即记录）；每层做选择 → 递归 → 撤销选择 | 全排列、子集、组合总和、N 皇后、括号生成 必背 |
| 剪枝技巧 | 可行性剪枝（超界直接 return）、最优性剪枝（当前已劣于已知最优）、排序后提前断路、记忆化去重 | 组合总和 II（排序后同层跳过）、单词搜索、数独（位运算候选集） |
| BFS vs DFS 选择 | 问「最短/最少步数」用 BFS；问「能否到达/连通性/枚举所有方案」用 DFS 或并查集；树题默认 DFS 递归 | 迷宫最短路用 BFS；连通分量数量两者皆可，DFS 代码更短 易混淆 |
🧮 动态规划
| 套路 | 要点 | 典型题 / 模板 |
|---|---|---|
| DP 四步法 | ① 定状态：dp[i] 的含义一句话说清；② 推转移：当前状态由哪些更小状态构成；③ 定初始化与边界；④ 定遍历顺序保证依赖已算好 | 写题先口头复述四步再动手；数组含义说不清必错 必背 |
| 01 背包 | 每件物品至多选一次；二维 dp[i][c] = 前 i 件容量 c 的最大价值；滚动数组需容量倒序遍历 | for i in 物品 for c = C..w[i] 倒序 dp[c] = max(dp[c], dp[c-w[i]] + v[i]) |
| 完全背包 | 物品可无限选：与 01 背包唯一区别是容量正序遍历（允许同层重复选） | 零钱兑换 II（组合数外层物品）、零钱兑换（最少硬币）、完全平方数 面试高频 |
| 分组背包 | 每组至多选一件：外层组、中层容量倒序、内层组内枚举选哪个 | for g in 组 for c = C..0 倒序 for x in 组 g dp[c] = max(dp[c], dp[c-w[x]] + v[x]) |
| LIS 最长递增子序列 | O(n²)：以 i 结尾的 dp[i] 取所有更小元素转移；O(n log n)：维护单调数组，二分查找替换位置 | 最长递增子序列、俄罗斯套娃信封（二维偏序） |
| LCS 最长公共子序列 | 二维 dp[i][j] = s 前 i 与 t 前 j 的 LCS；字符相等取左上 +1，否则取上/左最大 | 最长公共子序列、两个字符串的删除操作、不相交的线 |
| 编辑距离 | 双串二维 DP：相等则继承左上，否则增/删/改三种操作取最小 +1；初始化空串到 i 串需 i 次操作 | 编辑距离、不同的子序列、两个字符串的最小 ASCII 删除和 经典模型 |
| 打家劫舍（打家劫舍系列） | 线性 DP + 相邻约束：dp[i] = max(dp[i-1], dp[i-2] + v[i])；环形版拆成两次线性，树形版用「选/不选」双状态递归 | 打家劫舍、打家劫舍 II（环形）、打家劫舍 III（树形） |
🔙 回溯与贪心
| 套路 | 要点 | 典型题 / 模板 |
|---|---|---|
| 回溯模板 | 「做选择 → 递归 → 撤销选择」三步曲，递归树上每个节点维护当前路径与选择列表 | backtrack(路径, 选择列表) { if (满足结束条件) { 记录结果; return } for (选择 : 选择列表) { if (不合法) continue // 剪枝 做选择; backtrack(下一层); 撤销选择 } } |
| 去重技巧 | 先排序，再在「同一层」跳过与前一个相同的元素（i > start 且 a[i]==a[i-1] 则 continue），保证同层不重、纵向可重 | 子集 II、组合总和 II、全排列 II（配 used 数组）面试高频 |
| 组合 vs 排列 | 组合/子集：递归传 start 只向后选，天然去重；排列：每层都可从头选，需 used[] 标记已用元素 | 组合（start 剪枝 i <= n - (k - len) + 1）vs 全排列（used）易混淆 |
| 贪心适用条件 | 局部最优能推出全局最优（贪心选择性质 + 最优子结构），且无需回头修正；常用手段是先排序再贪 | 分发饼干、跳跃游戏、无重叠区间（按右端点排序）、分发糖果（两次遍历）必背 |
| 交换论证法 | 证明贪心正确性的标准套路：假设存在最优解与贪心选择不同，通过交换两个选择证明贪心同样不劣 | 区间调度按右端点排序的最优性证明（面试讲解加分项） |
| 贪心反例警示 | 零钱兑换（面额 1/3/4 凑 6）：贪心先取 4 得 3 枚，最优是 3+3 共 2 枚——面额不成倍数关系时贪心失效，须用 DP | 经典反例 凑硬币问题先问面额结构，再决定贪心还是 DP |
🧱 前缀和与差分
| 套路 | 要点 | 典型题 / 模板 |
|---|---|---|
| 一维前缀和 | pre[i] = pre[i-1] + a[i]，预处理 O(n)，任意区间和 O(1) 查询；下标从 1 开始可免边界判断 | sum(l..r) = pre[r] - pre[l-1] 和为 K 的子数组、区域和检索 必背 |
| 二维前缀和 | 容斥原理：加两次减一次的十字交叉；查询同样按容斥展开 | pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j] 二维区域和检索 面试高频 |
| 一维差分 | 前缀和的逆运算：区间 [l, r] 整体加 x 只需端点两笔操作，m 次区间修改 O(m) 完成 | d[l] += x; d[r+1] -= x 航班预订统计、拼车问题 |
| 二维差分 | 子矩阵整体加减：对四个角操作，容斥方向与前缀和相反 | d[x1][y1] += x; d[x2+1][y1] -= x d[x1][y2+1] -= x; d[x2+1][y2+1] += x |
| 差分还原 | 所有修改完成后做一遍前缀和即还原原数组：a[i] = a[i-1] + d[i] | 差分是「修改快」，前缀和是「查询快」：多次修改后统一还原 易混淆 |
| 典型题清单 | 识别信号：多次「区间加减」用差分；多次「区间求和」用前缀和；两者结合处理「修改后查询」 | 和为 K 的子数组（前缀和 + 哈希）、航班预订统计（差分）、合并区间（排序 + 扫描线思想） |
🧯 超时急救箱
TLE 不是重写信号，而是复杂度档位选错了：对症下药，一招把量级降下来。
| 超时症状 | 病因诊断 | 急救方案 |
|---|---|---|
| 双循环两两配对 TLE | O(n²) 在 n = 1e5 时约 1e10 次运算，必超时 | 内层查找换哈希表，一次遍历解决：两数之和、数组去重、缺失的第一个正数 |
| 有序数据线性扫描 | 每次全量扫 O(n)，q 次查询总计 O(nq) | 排序 + 二分，单次降到 O(log n)：查找插入位置、统计 ≥ x 的个数 |
| 枚举全部子串 | 子串 O(n²) 个，逐个校验再乘一个 n 直接爆炸 | 滑动窗口 + 计数器 O(n)：无重复最长子串、最小覆盖子串 |
| 递归重复算同一状态 | 指数级调用树里大量重叠子问题被反复计算 | 记忆化缓存「参数 → 结果」，或改自底向上 DP：爬楼梯、斐波那契、背包 |
| 大数运算溢出丢精度 | long 也装不下的累加、浮点比较时对时错 | 字符串按位模拟四则运算；加法用异或 + 进位；比较改判差值符号防溢出 |
| 频繁区间求和 / 增减 面试高频 | 每次都扫一遍区间，m 次操作 O(nm) | 静态多次查询用前缀和 O(1) 查；批量区间增减用差分，最后还原一次 |
🧨 调试锦囊
【调试模板】只在三类节点打印：循环入口、关键分支、出口
int round = 0; // 哨兵：防死循环
int prevL = -1, prevR = -1;
while (l < r) {
if (l == prevL && r == prevR)
print "区间不缩小 → mid 取整方向与边界更新不配套";
prevL = l; prevR = r;
mid = l + (r - l) / 2;
print "round=" + (++round) + " l=" + l + " r=" + r
+ " mid=" + mid + " a[mid]=" + a[mid]; // 循环变量
if (a[mid] < target) l = mid + 1; // 确认严格右移
else r = mid; // 确认不会跳回旧 mid
}
print "出口: l=" + l + " r=" + r; // 与预期下标人工比对
【检查点清单】
1. 循环前：打印 n 与边界初值，确认区间开闭定义与循环条件配套
2. 循环中：每轮打印循环变量 + 中间状态（窗口内容 / 当前和 / 计数器）
3. 死循环：连续两轮 [l, r] 完全不动 → 先查是否漏了 mid 上取整
4. 答案差一：出口多打印 l-1 与 l 两个候选下标，人工核对目标值
5. 递归题：入口打 (深度, 入参)、出口打 (深度, 返回值)，层数对不齐 = 漏 return