算法模板练习指南：二分、滑动窗口与动态规划核心解法

1. 为什么刷题容易白刷：模板练习解决的核心问题

1.1 刷题量上去了，面试还是卡壳

我见过很多准备算法面试的朋友，包括几年前的我，都会陷入同一个怪圈：LeetCode 刷了两三百道，Easy、Medium 见了不少，做题时也"好像见过类似的"，但一到面试现场，面对一道从没见过的变种题，思路就是出不来。更尴尬的是，面试官稍微追问一句"你这个解法的时间复杂度为什么是 O(n log n)"，很多人就开始含糊了。

问题出在哪？刷题的数量和题目的熟练度，并不能直接转化成"解题能力"。你记住的是每一道具体题目的答案，而不是题目背后那一套可以迁移的解题骨架。我把这个阶段叫做"背题阶段"，它和"模板练习阶段"最大的区别在于：背题是在记忆结果，模板练习是在提炼过程。

我记得特别清楚的一次，是在准备一家公司的二面时，出了一道"寻找旋转排序数组中的最小值"。这题我明明刷过，也知道要二分，但当时脑子里的二分模板全是"在有序数组中查找某个值"的那种写法，遇到"部分有序"的情况，边界条件怎么调都调不对。最后虽然磕磕绊绊写出来了，但明显暴露出了我对二分查找理解不深的问题。那次之后我才下决心，把基础算法的模板系统性地整理了一遍。

1.2 模板的本质：把"变量"和"不变式"分离开

说一个我一直强调的观点：算法模板不是让你背代码，而是帮你把一道题目拆成"不变的部分"和"可变的部分"。

以二分查找为例。不管题目是"查找目标值"、"查找第一个大于等于 target 的位置"，还是"查找旋转数组的最小值"，模板里不变的部分永远是：维护一个搜索区间、计算中点、根据条件收缩区间。可变的部分只有一个——收缩条件是什么。当你把模板练熟之后，做新题时你不需要从零开始推演整个算法，你只需要回答一个问题：这道题里，我应该在什么条件下把区间往左收、什么条件下往右收。

用更直白的话说，模板就是给你的解题过程提供一个"默认骨架"。就像写作文要先用"总—分—总"结构打底一样，骨架本身不产生内容，但它能保证你的思路不散。算法题也一样，排序、二分、双指针、滑动窗口、DFS、BFS、回溯、动态规划，这些基础算法一共就那么十几个大类，每一类你手上有一个信得过的模板，遇到新题时的第一反应就不再是"这题我不会"，而是"这题属于哪个模板的变体"。

1.3 哪些题适合模板化，哪些不适合

不是说所有题都要硬套模板。我总结过一个大致的划分，供你参考：

我见过一些人走到另一个极端，连贪心题都要强行总结模板，结果总结出来的东西根本没法迁移。基础算法模板练习的核心价值，是覆盖面试里出现频率最高的那批题型，而不是试图用模板包裹所有题目。下面我会按我自己的整理顺序，把最值得练的几套模板逐个拆开讲。

2. 从零搭建第一套算法模板：排序与二分查找

2.1 快速排序模板：分治思想的默认实现

很多人的排序是从调用sort()函数开始的，但面试里手写排序的概率虽然不高，理解排序背后的分治思想却很重要，因为快排和归并里面藏着面试题喜欢考的两个关键点：分区逻辑和递归边界。

先给一个我常用的快排模板：

def quick_sort(nums, left, right): if left >= right: return pivot = nums[(left + right) // 2] i, j = left, right while i <= j: while nums[i] < pivot: i += 1 while nums[j] > pivot: j -= 1 if i <= j: nums[i], nums[j] = nums[j], nums[i] i += 1 j -= 1 quick_sort(nums, left, j) quick_sort(nums, i, right)

这个模板和网上很多版本不太一样，我特别说明几个点。第一，pivot 取中点而不是取第一个或最后一个元素，这样可以避免在"数组已经有序"这种极端情况下退化成 O(n²)。第二，内层两个 while 用的是<和>而不是<=和>=，这样能保证相等的元素不会反复交换，让左右两边更均衡。第三，递归的边界是(left, j)和(i, right)，这个区间的划分方式和i <= j的交换逻辑是配套的，不能乱改。

实际练习的时候，我建议你在白纸上手动跑一遍[5, 2, 3, 1, 4]这个例子，把每一轮 i、j 的移动轨迹画出来。很多人觉得快排难，难就难在"为什么递归边界有时是 j 有时是 i"。当你手动推完一轮就会发现，pivot 被交换之后，i 左侧都是小于等于 pivot 的，j 右侧都是大于等于 pivot 的，所以两个递归区间天然就是[left, j]和[i, right]。

2.2 归并排序模板：除了排序还能求逆序对

归并排序的模板价值在于它的"合并"过程，这个过程不仅是排序，还是很多"区间统计类"题目的基础，最典型的就是求逆序对数量。

def merge_sort(nums, left, right): if left >= right: return 0 mid = (left + right) // 2 count = 0 count += merge_sort(nums, left, mid) count += merge_sort(nums, mid + 1, right) # 合并两个有序区间 temp = [] i, j = left, mid + 1 while i <= mid and j <= right: if nums[i] <= nums[j]: temp.append(nums[i]) i += 1 else: temp.append(nums[j]) count += mid - i + 1 # 关键：左区间剩余元素都大于 nums[j] j += 1 while i <= mid: temp.append(nums[i]) i += 1 while j <= right: temp.append(nums[j]) j += 1 nums[left:right + 1] = temp return count

这里唯一需要理解透的就是count += mid - i + 1这一行。当右区间的nums[j]比左区间的nums[i]小时，说明从 i 到 mid 的所有元素都比nums[j]大，这些元素都和nums[j]构成逆序对，数量正好是mid - i + 1个。这个技巧在"计算右侧小于当前元素的个数"这类 LeetCode 题里会直接用到，你如果只会调sort()，面对这类题就只能用树状数组硬写，复杂度没优势，代码还复杂得多。

2.3 二分查找的三种模板与边界陷阱

二分是面试里最容易被"细节打败"的基础算法。我见过太多人在循环条件上用left < right还是left <= right之间反复横跳，就是因为没有建立一套统一的"循环不变量"。

我自己的做法是只记一套主模板，然后用"查找左边界"和"查找右边界"两个小变体去覆盖所有场景。主模板如下：

def binary_search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1

这个模板的循环不变量是：target 如果存在，一定在闭区间[left, right]内。每次比较后，left = mid + 1或right = mid - 1都能保证区间严格缩小，所以循环一定终止。

但实际面试题里更常考的是"查找第一个大于等于 target 的位置"，也就是lower_bound，这就是另一个模板：

def lower_bound(nums, target): left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] >= target: right = mid else: left = mid + 1 return left

注意这里的循环条件变成了left < right，区间变成了左闭右开的[left, right)，而且找到了目标也不返回，而是继续把right收到mid。这就是"查找左边界"和"查找指定值"在写法上的本质区别：前者关心的是"第一个满足条件的位置"，后者关心的是"有没有这个值"。你在练的时候，一定要在纸上各画三个例子：目标在数组中间、目标比所有元素都大、目标不存在但落在区间内，把这三种情况跑通，二分才算真正过关。

提示：二分查找里mid = left + (right - left) // 2避免写成(left + right) // 2，主要是防止两个很大的整数相加溢出。Python 里其实不容易溢出，但养成这个习惯没有坏处。

3. 双指针与滑动窗口：两类高频模板的边界处理

3.1 相向双指针：有序数组的经典套路

双指针分为两类，一类是"相向而行"，典型题目就是 LeetCode 的"两数之和 II"和"盛最多水的容器"；另一类是"同向而行"，就是滑动窗口。两类的模板差异很大，先说相向双指针。

def two_sum_sorted(nums, target): left, right = 0, len(nums) - 1 while left < right: s = nums[left] + nums[right] if s == target: return [left + 1, right + 1] elif s < target: left += 1 else: right -= 1 return []

这个模板的前提是数组有序。当nums[left] + nums[right] < target时，说明当前右指针指向的是数组最大值，左指针再往右走一步，和会变大；反之亦然。每一步都排除掉一个不可能的位置，所以时间复杂度是 O(n)，空间 O(1)。这种"根据单调性排除不可能区间"的思路，是双指针模板最核心的价值。

我在练习中还发现一个容易忽略的点：相向双指针不只适用于有序数组，只要问题的单调性成立就能用。"盛最多水的容器"这个题里，数组本身无序，但"移动较短的那端"这个决策是有单调性保证的——移动短板可能让面积变大，移动长板只会让面积变小或不变，所以双指针依然成立。练这种题的时候，不要只记模板，要把"为什么可以这样移动"的理由写下来，这才是模板真正内化的标志。

3.2 同向双指针与滑动窗口模板

滑动窗口是面试里出现频率最高的题型之一，覆盖了"无重复字符的最长子串"、"最小覆盖子串"、"长度最小的子数组"等一系列基础题。它本质上是一个"维护可变长度窗口"的模板：

def sliding_window(s, k): n = len(s) left = 0 window = {} # 或者用 Counter result = 0 for right in range(n): # 1. 扩展窗口，加入 s[right] window[s[right]] = window.get(s[right], 0) + 1 # 2. 收缩窗口：当窗口不满足条件时，移动 left while not_meet_condition(window): window[s[left]] -= 1 if window[s[left]] == 0: del window[s[left]] left += 1 # 3. 此时窗口满足条件，记录/更新结果 result = max(result, right - left + 1) return result

这个模板的骨架就是"扩展—收缩—记录"三步，任何滑动窗口题都逃不出这个流程。你需要变的部分只有两个：window里存什么，以及not_meet_condition怎么定义。

以"无重复字符的最长子串"为例，条件就是"窗口内所有字符的出现次数都等于 1"，一旦某个字符出现次数大于 1，就说明有重复，需要收缩。而以"长度最小的子数组"为例，窗口里存的是数值和，条件是"当前窗口的和大于等于 target 就收缩并记录长度"。你会发现只要把这两处填进模板，题目就解完了。

3.3 窗口收缩时机：模板中最容易写错的一行

我在带人刷题时发现，滑动窗口模板最容易写错的不是扩展，而是收缩那部分的"谁先谁后"。

这里有一个关键原则：先更新窗口数据，再移动 left 指针。很多人会写成先移动 left 再减去字符次数，导致窗口里的数据和实际区间对不上。另外一个容易错的是，收缩循环里的"记录结果"位置——是在收缩前记录，还是收缩后记录？这取决于你要求的是"满足条件的最小窗口长度"还是"满足条件的最长窗口长度"。

如果题目要求"最小覆盖子串"这类找最短的，你需要在找到满足条件的窗口时先记录长度，再继续收缩，因为收缩可能得到更短的结果。如果要求"无重复最长子串"这类找最长的，你应该在收缩完成后记录，因为收缩前窗口是无效的。这两个方向反了，很多题就是过不了。

# 找最短：先记录，再收缩 for right in range(n): window.add(s[right]) while is_valid(window): result = min(result, right - left + 1) # 记录有效状态 window.remove(s[left]) left += 1 # 找最长：先收缩，再记录 for right in range(n): window.add(s[right]) while not is_valid(window): window.remove(s[left]) left += 1 result = max(result, right - left + 1) # 收缩后才是有效状态

这两段代码我建议你单独练熟，然后在"滑动窗口最大值"这类进阶题里继续复用。模板的价值就体现在这里——你不需要重新想整个流程怎么设计，只需要调到窗口里的"单调队列"结构即可。

4. 图论与搜索模板：DFS、BFS与回溯

4.1 DFS模板：遍历与路径记录

深度优先搜索是所有图论题的基础。面试里考 DFS 的题目基本绕不开"岛屿数量"、"矩阵中的路径"、"全排列"这几类。它们的核心模板是一致的：

def dfs(grid, i, j, visited): # 1. 越界或非法状态，返回 if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != target: return # 2. 标记已访问，避免重复遍历 if (i, j) in visited: return visited.add((i, j)) # 3. 递归处理四个方向的邻居 for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]: dfs(grid, i + di, j + dj, visited)

这个模板的核心变量只有一个：grid[i][j] != target这个条件。岛屿数量题里，target是'1'；矩阵路径题里，target是当前需要的字符。你不需要改递归结构，只需要改这个判断条件。

我在实际练习中有一个经验：DFS 在"统计连通块数量"和"判断是否存在路径"这两类问题里，区别只在于你有没有在递归返回时"恢复现场"。统计连通块只需要标记访问，而"是否存在从起点到终点的路径"这类题目，通常需要一个返回值True/False，并且在四个方向的递归中，只要有一个方向返回 True，就要提前返回。

4.2 BFS模板：最短路径的层序遍历写法

BFS 和 DFS 的区别在于搜索顺序，BFS 按"层"推进，天然适合求最短路径。模板如下：

from collections import deque def bfs(start, target): queue = deque([start]) visited = set([start]) steps = 0 while queue: size = len(queue) for _ in range(size): node = queue.popleft() if node == target: return steps for neighbor in get_neighbors(node): if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) steps += 1 return -1

这个模板里最容易出问题的点，是size = len(queue)这一行。很多人会直接把队列里的元素一个个 popleft，然后steps += 1放错位置，导致步数统计错误。正确的做法是：在每层开始前取一次当前队列长度，这一层的节点全部处理完，步数才加一。

提示：BFS 的 visited 数组标记的时机应该在"入队时"而不是"出队时"。如果在出队时才标记，同一个节点可能被多个邻居重复加入队列，极端情况下会指数级膨胀。这是我见过的 BFS 实现里最常见的一个性能隐患。

BFS 模板还有一个很重要的变体：当状态空间很大、每一步的状态可以表示成多个维度时，visited 要用适当的数据结构。比如"打开转盘锁"这个题，每个状态是一个四位字符串，visited 用 set 存字符串就完全没问题；但如果状态是二维坐标，用二维数组或 set of tuple 都可以。

4.3 回溯模板：组合、排列、子集的统一写法

回溯是 DFS 在"组合优化"问题里的特殊应用，模板和普通 DFS 最大的区别在于多了"撤销选择"这一步。LeetCode 里"组合总和"、"全排列"、"子集"这三类题，都可以用同一套回溯模板解决：

def backtrack(path, start): # 记录合法结果 if is_solution(path): result.append(path[:]) # 注意拷贝 return for i in range(start, len(nums)): # 剪枝条件（可选） if is_pruned(i): continue path.append(nums[i]) backtrack(path, i + 1) # 组合：i+1 表示不重复取 path.pop() # 撤销选择

这套模板能覆盖的题型包括了"子集"（不限制长度，start 从 0 开始）、"组合"（限制长度，达到 k 个就记录）、"排列"（不是用 start 控制，而是每次从 0 开始遍历，配合 used 数组去重）。

排列和组合在模板上差一个参数：

def backtrack_permute(path, used): if len(path) == len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] = True path.append(nums[i]) backtrack_permute(path, used) path.pop() used[i] = False

我在练习时的体会是：回溯模板非常依赖"撤销选择"这一步是否写完整。很多人递归写完了，忘了path.pop()或者忘了改回used[i] = False，结果状态被污染，整个搜索树上所有分支都出错。一个实用技巧是：每当你发现回溯的结果里出现"重复的路径"，先检查撤销逻辑，大概率是状态没有恢复干净。

另外一个容易忽略的细节是result.append(path[:])里的[:]。如果直接append(path)，list 是引用传递，后面path.pop()会把你已经记录的结果也改掉。这个错误几乎每个新手都会犯一次，我建议你第一次练回溯模板时故意写错，看上几遍输出，印象会特别深刻。

5. 动态规划模板：状态定义、转移方程与初始化

5.1 线性DP模板：从定义状态到填表

动态规划是基础算法里最需要"悟性"的部分，但它的练习流程其实是有模板的。我总结的流程永远是三步：定义状态、写出转移方程、确定初始化和遍历顺序。以最经典的"最长递增子序列"为例：

def length_of_LIS(nums): n = len(nums) dp = [1] * n for i in range(n): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)

这个题的状态定义是dp[i]表示"以 nums[i] 结尾的最长递增子序列长度"。为什么是"以 i 结尾"而不是"前 i 个数"？因为递增子序列有连续性要求，只有知道结尾元素才能判断下一个元素能不能接上。这个"结尾状态"的思考方式，是线性 DP 最重要的模板化思维。

对比"打家劫舍"这个题，状态定义又不一样了：

def rob(nums): n = len(nums) if n == 1: return nums[0] dp = [0] * n dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, n): dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) return dp[n - 1]

这个题的状态定义是"到第 i 个房子时能偷到的最大金额"，转移方程的核心是"偷不偷当前这间房"两个选择。你会发现，线性 DP 的模板不是代码层面的，而是思维层面的：先把状态拆成"前 i 个元素 + 若干附加状态（结尾/是否占用）"，再把转移关系写成"上一状态到当前状态的所有合法路径取最优"。只要这个套路熟练了，面对新题你至少知道从哪里开始想。

5.2 背包问题的模板化写法

背包问题在面试里出现频率也很高，尤其是 0-1 背包和完全背包。它们的模板区别只在一个地方：内层循环的遍历方向。

# 0-1 背包：内层倒序遍历 def zero_one_knapsack(weights, values, capacity): dp = [0] * (capacity + 1) for i in range(len(weights)): for c in range(capacity, weights[i] - 1, -1): dp[c] = max(dp[c], dp[c - weights[i]] + values[i]) return dp[capacity] # 完全背包：内层正序遍历 def complete_knapsack(weights, values, capacity): dp = [0] * (capacity + 1) for i in range(len(weights)): for c in range(weights[i], capacity + 1): dp[c] = max(dp[c], dp[c - weights[i]] + values[i]) return dp[capacity]

为什么 0-1 背包要倒序？因为dp[c - weights[i]]在倒序遍历时是上一件物品的状态，正序遍历时则可能是当前物品已经被取过一次的状态，后者恰好就是完全背包允许重复取用的情况。这个倒序/正序的选择，是整个背包问题最核心的记忆点，理解了它，你就不需要死记"0-1 倒序、完全正序"这个口诀了。

5.3 区间DP和DP优化的边界考量

区间 DP 是动态规划里相对进阶的一类，典型题目是"最长回文子序列"和"戳气球"。模板套路是：

def longest_palindrome_subseq(s): n = len(s) dp = [[0] * n for _ in range(n)] for i in range(n - 1, -1, -1): dp[i][i] = 1 for j in range(i + 1, n): if s[i] == s[j]: dp[i][j] = dp[i + 1][j - 1] + 2 else: dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) return dp[0][n - 1]

区间 DP 最关键的是遍历顺序：i从大到小，j从小到大，保证计算dp[i][j]时，它所依赖的dp[i + 1][...]和dp[...][j - 1]都已经被算出来。我在练习时吃过一次亏，把i也从小到大遍历，结果很多状态依赖的是还没算出来的值，答案自然是错的。

DP 优化这块，基础阶段先不用深究，知道"状态压缩"和"斜率优化"这些名词就够了。面试中如果能把 O(n²) 的解法写对、讲清楚，已经能覆盖绝大多数动态规划题目。至于那些需要优化到 O(n) 的状态压缩，等你把基础模板都练熟了再逐个击破也不迟。

6. 我的模板练习路线图与实测避坑

6.1 90天练习计划怎么排

很多人的模板练习坚持不下去，是因为上来就对着 LeetCode 题单硬刷，刷到一半发现题目之间的关联度太低，很难形成体系。我自己当年重新整理模板时的路线是分阶段的，这里分享给你参考。

第一阶段（前两周）：只练"写模板"这件事。把排序、二分、双指针、滑动窗口这四类模板每天手写一遍，不刷题，只默写代码。目标是把代码写得和呼吸一样自然，不需要思考。

第二阶段（第3到6周）：每类模板配 10 到 15 道基础题，全部用模板去套。比如二分模板配的题就是"搜索旋转排序数组"、"寻找峰值"、"爱吃香蕉的珂珂"这类。这一阶段刻意不碰难题，目的是验证模板的覆盖面。

第三阶段（第7到10周）：开始做"模板融合题"。比如"滑动窗口 + 哈希表"、"二分 + 贪心"、"BFS + 状态压缩"，这些题需要对多个模板都足够熟练，才能组合使用。

第四阶段（最后两周）：回归，把第一阶段默写过的所有模板再默写一遍，然后对照自己的错题本，看哪些模板在实际使用中最容易出边界问题。

我自己的实测经验是：这个路线走下来，大概需要 250 到 300 道题，但每一道都是"带着模板去套"而不是"看着答案去背"。效果上的区别是，面试时遇到"从没见过的题"，你能很快说出"这个题本质上是区间 DP 的变体，我可以用区间 DP 模板来套"，这种判断力才是模板练习真正带来的东西。

6.2 复盘方法：模板卡片的维护

模板练习不能只靠刷题，复盘更重要。我习惯给每一类模板建一张"模板卡片"，卡片上写五块内容：模板代码、适用条件、边界陷阱、经典例题、易混淆题型。

举个例子，二分查找的模板卡片上，适用条件我会写"问题具有单调性，可以将搜索空间不断缩小"，边界陷阱写"循环条件 left <= right vs left < right 取决于区间定义"，易混淆题型写"最大值最小化问题（二分答案）和普通查找不同，需要 while left < right + 判断条件的写法"。

这种卡片不需要多么精美，一张纸或者一个 Markdown 文件就够。关键是每当你刷完一道题发现"这个题我的模板套不上"或者"套上了但边界条件写错了"，当场就要去更新对应的卡片。我后来翻自己的卡片发现，90% 的更新集中在两个地方：一是窗口收缩的时机，二是二分查找的边界条件。这两处更新多了，自然就形成肌肉记忆了。

6.3 模板练习不是终点：从模板到内化的最后一公里

最后我想说一点个人体会。模板练习的真正目标，不是让你成为一个只会套模板的"模板机器"，而是让你通过这些固定骨架，把基础算法里的核心思想内化成自己的思维方式。

我见过有人把模板背得滚瓜烂熟，但面试官问"你这个双指针为什么不会错过答案"的时候，完全答不上来。这说明他练的是"形"，不是"神"。我的建议是，在练每一类模板的时候，都花一点时间回答三个问题：为什么这个模板是对的？为什么边界条件必须这样处理？如果去掉某个条件，模板为什么失效？

比如滑动窗口模板，你要能解释清楚"为什么 right 指针只需要向前移动而不用回退"。原因在于，当窗口收缩到满足条件时，任何以当前 right 为右端点的、更短的合法窗口，都只能在 left 继续右移时出现，而 left 已经在 while 循环里推进到最远了。这个推理过程比模板本身更有价值。

我在实际练习中的体会是，模板练习和算法理解是互相成就的。先把模板写熟，再回头去理解原理，比一上来就死磕原理效率高得多；但只练模板不去理解原理，又会在变种题面前露怯。如果你正准备面试或者正在刷基础算法，我建议你从今天开始，选一个模板（比如二分查找），把它写到滚瓜烂熟，然后挑一道你没做过的二分变种题试试。你会发现，当你手上有一个信得过的模板时，面对新题的底气会完全不一样。