尧图网页设计 
刷 LeetCode 这件事最打击人的往往不是题目本身有多难而是“明明同类型题刷过不少换一个场景、换一组条件立刻认不出来”。尤其是准备校招、社招算法面试的同学每天都和每日一题、LeetCode 周赛 430 这种新题打交道如果只靠背题干和堆题量很容易陷入“刷了 200 题仍怕新题”的困境。其实 LeetCode 考察的算法思维是相对有限的。无论题目包装成数组、字符串、矩阵还是链表最终基本都会落到少数几种“解题模式”上。本文把这几年面试题和竞赛题里出现频率最高的 8 种 LeetCode 解题模式总结成一套方法每种模式都给出可复制的代码模板和典型题目你可以把模板直接拿去做专项练习也可以用这套框架去分析 LeetCode 热门 100 题。新手建议按顺序阅读有基础的也可以直接跳到某一节对照排查。1. 为什么刷了很多题遇到新题还是不会做先看一个很常见的现象把算法题当作“记忆题”来刷。今天刷了链表反转背下迭代写法明天刷二叉树层序遍历背下队列模板后天刷两数之和背下哈希表写法。看起来每天都在做题实际上只是把每个题单独记忆题目之间的共性并没有被抽象出来。一旦题目条件稍作修改或者从英文翻译过来的题干比较绕记忆匹配失败思路就断了。LeetCode 真正考察的不是几千道题的题库而是有限几种思维模型的迁移能力。所谓解题模式就是把一类看起来不同、但底层结构相同的问题归纳成同一个解法框架。例如下面四个问题数据都是nums [1, 2, 3]目标值都是 3但“目标形式”完全不同问题形态典型提问对应模式找两个数使和等于 target“返回下标”双指针 / 哈希统计连续子数组和为 target 的个数“有多少个连续子数组”前缀和 哈希枚举组合使元素和等于 target“返回所有组合”回溯每个数可选可不选求到达 target 的方案数“返回方案数”0/1 背包动态规划同一种数据同一个目标数字四个问题分别属于四种完全不同的模式。如果不能先判断“题目让我输出什么、具有什么约束”直接套代码必然错。周赛和每日一题之所以能拉开差距不是因为出现了全新算法而是因为新题经常给旧模式换一层业务皮肤。你能不能在读完题后快速判断出“这题本质是二分答案”“这题本质是滑动窗口”决定了你能不能按时 AC。这套能力不靠硬背靠对模式特征的系统总结。2. 解题模式识别的底层方法在给模板前先建立一套“模式识别”的思考顺序。拿到一道题不要急着写代码按下面三步走。2.1 先看输出目标题目问什么直接决定算法类型问“是否存在、是否能到达”通常是 DFS、BFS或哈希表判断。问“有多少种方案”优先考虑动态规划、回溯、组合数学。问“最大/最小/最短”滑动窗口、二分答案、BFS 最短路、动态规划需要根据数据结构再细化。问“列出所有具体方案”回溯几乎是默认答案。问“第 K 大 / 前 K 个高频”排序、堆、快速选择。2.2 再看数据范围LeetCode 题目会在 constraints 中明确数组长度这是很关键的提示n ≤ 20大概率可以暴力、DFS 全排列、状态压缩。n ≤ 10^3O(n²) 可以接受双层循环或者二维 DP。n ≤ 10^5需要 O(n log n) 或 O(n)排序、二分、双指针、堆等。n ≤ 10^6 及以上基本只能 O(n)参考前缀和、滑动窗口、哈希。很多新手不看 constraints直接写回溯超时后再看题解发现最优解只需要一次遍历。先估复杂度能筛掉大量错误方向。2.3 最后抓题目关键词有一些关键词可以帮我们快速定位候选模式“连续子数组/子串” → 前缀和、滑动窗口。“有序数组” → 双指针、二分。“单调性/最大化最小值/最小化最大值” → 二分答案。“所有组合/排列/路径” → 回溯。“从矩阵某区域向外扩散、感染” → BFS / DFS。“数据流中求中位数、Top K” → 堆。下面这张模式识别表可以在刷题初期贴在边上做参考题干信号目标类型首选模式连续区间和、区间数量统计数量/区间和前缀和哈希有序数组两两组合、反转数组找满足条件的对双指针子串/子数组长度最大或最小连续区间最优滑动窗口值域单调、可以 check 可行性最小/最大可行值二分答案子集、组合、排列、棋盘路径所有解回溯当前状态依赖前面状态最优值/方案数动态规划图/矩阵连通性、最短扩散步数是否存在/最短步数BFS / DFS第 K 大/前 K 高频Top K堆模式识别不是玄学。多刷题后你会发现每道题都等于“数据结构 算法模式 边界条件”。模板解决的是中间的算法模式部分边界条件和题目细节仍然需要你认真读题。3. 八种高频 LeetCode 解题模式与代码模板3.1 前缀和处理“连续子数组求区间和”类问题前缀和是一种用空间换时间的经典预处理。定义数组pre[i]表示原数组前 i 个元素的和那么[l, r)这个左闭右开区间的和可以用pre[r] - pre[l]一步得到。遇到连续子数组求和类问题前缀和可以把 O(n²) 的区间枚举降到 O(1) 查询如果再配合哈希表还能解决“和为 target 的连续子数组个数”这类问题典型代表是 LeetCode 560。模板代码可直接在 LeetCode 560 中提交from typing import List from collections import defaultdict class Solution: def subarraySum(self, nums: List[int], k: int) - int: pre 0 cnt defaultdict(int) cnt[0] 1 ans 0 for x in nums: pre x # 如果之前存在 pre - k意味着存在连续子数组和为 k ans cnt[pre - k] cnt[pre] 1 return ans理解这段代码的关键是“哈希表存的是前缀和出现的次数”。我们遍历数组时维护当前前缀和pre如果曾经出现过前缀和pre - k那么从那个位置之后到当前位置的这段连续子数组和就是 k。常见误区经典前缀和数组写法中pre长度是n 1下标要错开否则很容易越界。哈希表写法里的cnt[0] 1也不能漏它表示“前缀和为 0 出现了一次”对应子数组从数组开头开始的场景。典型题目LeetCode 303 区域和检索、LeetCode 560 和为 K 的子数组、LeetCode 437 路径总和 III把树路径也用前缀和思路处理。3.2 双指针有序数组与链表问题的高效解法双指针并不是某一种专属数据结构它有两种常见形态第一种是对撞指针常用于有序数组。初始化left指向开头、right指向结尾根据当前两个指针指向元素的和与 target 的大小关系决定移动哪一侧。因为数组有序指针移动方向是确定的所以不会漏解。以 LeetCode 167 两数之和 II 为例from typing import List class Solution: def twoSum(self, numbers: List[int], target: int) - List[int]: left, right 0, len(numbers) - 1 while left right: total numbers[left] numbers[right] if total target: return [left 1, right 1] if total target: left 1 else: right - 1 return [-1, -1]每次移动一个位置最多遍历完整数组一次时间复杂度 O(n)。这里能这样移动的前提是数组已经非递减排序如果数组未排序就需要先排序或改用哈希表。第二种是快慢指针。经典场景是链表快指针每次走两步慢指针每次走一步。如果链表存在环快指针一定会追上慢指针因此可以判断链表是否有环并找到环的入口。双指针模式的核心价值在于把“两两组合”的 O(n²) 暴力枚举降到 O(n)。LeetCode 15 三数之和、LeetCode 11 盛最多水的容器都是同一种思维。易错点使用对撞指针时注意别在循环内同时无脑移动两个指针。三数之和这类题目还要在获得答案后跳过重复元素否则结果会产生重复三元组。3.3 滑动窗口子串和子数组的“定长/变长”控制滑动窗口和双指针容易混淆但关注点不同。滑动窗口通常处理的是“连续子串、连续子数组满足某个条件”的问题窗口由左边界left和右边界right共同维护。右指针不断扩张把新元素纳入窗口当窗口不再满足题目要求时左指针收缩窗口直到窗口恢复合法。以 LeetCode 209 长度最小的子数组为例题目要求找出最短的连续子数组使其和大于等于 targetfrom typing import List class Solution: def minSubArrayLen(self, target: int, nums: List[int]) - int: n len(nums) left 0 total 0 ans float(inf) for right in range(n): total nums[right] while total target: ans min(ans, right - left 1) total - nums[left] left 1 return 0 if ans float(inf) else ans这段代码里for right in range(n)负责扩展窗口while total target负责判断窗口是否要收缩。每次收缩前都会尝试更新答案因为收缩后窗口不再满足条件所以合法窗口只可能在收缩前出现。易错点有的题目窗口收缩条件复杂例如 LeetCode 76 最小覆盖子串需要维护“每种字符还需要多少个”的欠账数量。如果只记住“至少包含 target 字符”这个表面条件很容易把 left 的收缩条件写错。建议把“窗口满足什么条件”单独抽成一个变量来表示例如valid或need_cnt而不是在 while 条件里临时统计。滑动窗口能够把 O(n²) 的枚举子串优化到 O(n)因为每个元素最多被 right 加入一次、被 left 移出一次。3.4 二分查找与二分答案单调性比“有序数组”更本质很多初学二分时只知道“在有序数组里查找 target”但 LeetCode 里大量题目并不是直接查找数组元素而是“搜索答案”。这类题有一个明显特征答案在一个整数区间里并且随着答案增大题目给定的判定结果呈现单调变化。先看标准二分查找模板找有序数组中第一个大于等于 target 的位置from typing import List def lower_bound(nums: List[int], target: int) - int: lo, hi 0, len(nums) while lo hi: mid (lo hi) // 2 if nums[mid] target: lo mid 1 else: hi mid return lo这段代码使用左闭右开区间循环条件是lo hi。当nums[mid] target时说明 mid 以及左侧都不可能满足因此lo mid 1否则hi mid。最终lo就是第一个满足条件的位置。二分答案的通用模板如下def can(mid) - bool: # 根据题目实现判断答案 mid 是否可行 pass lo, hi 0, max_possible_answer # 根据题目确定值域 while lo hi: mid (lo hi) // 2 if can(mid): hi mid # mid 可行尝试更小的答案 else: lo mid 1 # mid 不可行答案必须更大 return lo很多看起来完全不沾边的题都能套这个模板。例如“爱吃香蕉的狒狒”LeetCode 875虽然问的是吃香蕉速度但速度越大吃完所需时间越短满足单调性在速度区间上二分即可。具体推导会在第 5 节展开。易错点二分最容易错的是边界和死循环。统一使用“左闭右开 lo hi 更新lo mid 1或hi mid”可以避免很大一部分死循环问题。不要混用不同模板。3.5 回溯子集、组合、排列的统一解决方案回溯本质是带剪枝的深度优先搜索。很多题目要求“返回所有满足条件的方案”这类结果数量多无法用普通 DP 直接计数于是选择系统的搜索树遍历。回溯核心代码只有三步做选择、递归、撤销选择。以 LeetCode 39 组合总和为例数字可以被重复使用from typing import List class Solution: def combinationSum(self, candidates: List[int], target: int) - List[List[int]]: ans [] path [] def dfs(start: int, rest: int) - None: if rest 0: ans.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] rest: continue path.append(candidates[i]) dfs(i, rest - candidates[i]) # 允许重复所以从 i 开始 path.pop() dfs(0, target) return ans这里可以用单个start参数控制组合不允许重复的无序性。如果是求全排列每个元素只能使用一次且顺序不同算不同答案则需要用used数组标记哪些元素已经被选到当前路径中。回溯的两种形态要区分清楚组合型问题用start控制下一层只能从后面元素开始。排列型问题用used每个元素只能选一次但顺序可变。当原始数组本身包含重复数字且要求结果不能重复时先排序再在 for 循环内判断if i start and nums[i] nums[i - 1]: continue这行剪枝的含义是“同一层递归中跳过已经处理过的相同数字”。回溯复杂度通常不可接受因为它本来就是在暴力搜索全部解。真正考察的是你是否通过 sort、start、used 和可行性剪枝减少了无效路径。写递归时尽量用局部变量维护path并记得在递归返回后pop()否则结果会出现残留。3.6 动态规划状态定义比转移模板更重要动态规划是许多开发者的痛点因为它不像回溯那样有一个万能 for 循环模板。但反过来看动态规划的代码量往往很短难点集中在“状态定义”和“状态转移”上。最基础的入门模型是线性 DP。以 LeetCode 198 打家劫舍为例不能偷相邻房屋求最大金额from typing import List class Solution: def rob(self, nums: List[int]) - int: n len(nums) if n 0: return 0 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]dp[i]表示偷到第 i 间房屋时能获得的最大金额。对第 i 间房屋只有两种选择不偷则dp[i] dp[i-1]偷则第 i-1 间不能偷当前值等于dp[i-2] nums[i]。二者取最大即可。另一个高频模型是背包 DP特别是在“每个元素选或不选、计算方案数/能否组成某值”的题目中0/1 背包的一维数组模板是必须掌握的dp [0] * (capacity 1) dp[0] 1 for x in nums: for c in range(capacity, x - 1, -1): dp[c] dp[c - x] # 方案数版如果是最大价值改成 max() return dp[capacity]这里的关键点是内层循环必须倒序否则同一个元素会被重复使用变成完全背包。如果你发现“每个物品只能选一次但结果偏大”通常就是内层循环方向写反了。动态规划没有“一招鲜”的模板建议按题型积累线性 DP、背包 DP、区间 DP、状态压缩 DP。遇到新题时不要急着找模板先定义状态dp[i] LeetCode 刷题总是没思路？掌握这 8 种高频解题模式与代码模板
刷 LeetCode 这件事最打击人的往往不是题目本身有多难而是“明明同类型题刷过不少换一个场景、换一组条件立刻认不出来”。尤其是准备校招、社招算法面试的同学每天都和每日一题、LeetCode 周赛 430 这种新题打交道如果只靠背题干和堆题量很容易陷入“刷了 200 题仍怕新题”的困境。其实 LeetCode 考察的算法思维是相对有限的。无论题目包装成数组、字符串、矩阵还是链表最终基本都会落到少数几种“解题模式”上。本文把这几年面试题和竞赛题里出现频率最高的 8 种 LeetCode 解题模式总结成一套方法每种模式都给出可复制的代码模板和典型题目你可以把模板直接拿去做专项练习也可以用这套框架去分析 LeetCode 热门 100 题。新手建议按顺序阅读有基础的也可以直接跳到某一节对照排查。1. 为什么刷了很多题遇到新题还是不会做先看一个很常见的现象把算法题当作“记忆题”来刷。今天刷了链表反转背下迭代写法明天刷二叉树层序遍历背下队列模板后天刷两数之和背下哈希表写法。看起来每天都在做题实际上只是把每个题单独记忆题目之间的共性并没有被抽象出来。一旦题目条件稍作修改或者从英文翻译过来的题干比较绕记忆匹配失败思路就断了。LeetCode 真正考察的不是几千道题的题库而是有限几种思维模型的迁移能力。所谓解题模式就是把一类看起来不同、但底层结构相同的问题归纳成同一个解法框架。例如下面四个问题数据都是nums [1, 2, 3]目标值都是 3但“目标形式”完全不同问题形态典型提问对应模式找两个数使和等于 target“返回下标”双指针 / 哈希统计连续子数组和为 target 的个数“有多少个连续子数组”前缀和 哈希枚举组合使元素和等于 target“返回所有组合”回溯每个数可选可不选求到达 target 的方案数“返回方案数”0/1 背包动态规划同一种数据同一个目标数字四个问题分别属于四种完全不同的模式。如果不能先判断“题目让我输出什么、具有什么约束”直接套代码必然错。周赛和每日一题之所以能拉开差距不是因为出现了全新算法而是因为新题经常给旧模式换一层业务皮肤。你能不能在读完题后快速判断出“这题本质是二分答案”“这题本质是滑动窗口”决定了你能不能按时 AC。这套能力不靠硬背靠对模式特征的系统总结。2. 解题模式识别的底层方法在给模板前先建立一套“模式识别”的思考顺序。拿到一道题不要急着写代码按下面三步走。2.1 先看输出目标题目问什么直接决定算法类型问“是否存在、是否能到达”通常是 DFS、BFS或哈希表判断。问“有多少种方案”优先考虑动态规划、回溯、组合数学。问“最大/最小/最短”滑动窗口、二分答案、BFS 最短路、动态规划需要根据数据结构再细化。问“列出所有具体方案”回溯几乎是默认答案。问“第 K 大 / 前 K 个高频”排序、堆、快速选择。2.2 再看数据范围LeetCode 题目会在 constraints 中明确数组长度这是很关键的提示n ≤ 20大概率可以暴力、DFS 全排列、状态压缩。n ≤ 10^3O(n²) 可以接受双层循环或者二维 DP。n ≤ 10^5需要 O(n log n) 或 O(n)排序、二分、双指针、堆等。n ≤ 10^6 及以上基本只能 O(n)参考前缀和、滑动窗口、哈希。很多新手不看 constraints直接写回溯超时后再看题解发现最优解只需要一次遍历。先估复杂度能筛掉大量错误方向。2.3 最后抓题目关键词有一些关键词可以帮我们快速定位候选模式“连续子数组/子串” → 前缀和、滑动窗口。“有序数组” → 双指针、二分。“单调性/最大化最小值/最小化最大值” → 二分答案。“所有组合/排列/路径” → 回溯。“从矩阵某区域向外扩散、感染” → BFS / DFS。“数据流中求中位数、Top K” → 堆。下面这张模式识别表可以在刷题初期贴在边上做参考题干信号目标类型首选模式连续区间和、区间数量统计数量/区间和前缀和哈希有序数组两两组合、反转数组找满足条件的对双指针子串/子数组长度最大或最小连续区间最优滑动窗口值域单调、可以 check 可行性最小/最大可行值二分答案子集、组合、排列、棋盘路径所有解回溯当前状态依赖前面状态最优值/方案数动态规划图/矩阵连通性、最短扩散步数是否存在/最短步数BFS / DFS第 K 大/前 K 高频Top K堆模式识别不是玄学。多刷题后你会发现每道题都等于“数据结构 算法模式 边界条件”。模板解决的是中间的算法模式部分边界条件和题目细节仍然需要你认真读题。3. 八种高频 LeetCode 解题模式与代码模板3.1 前缀和处理“连续子数组求区间和”类问题前缀和是一种用空间换时间的经典预处理。定义数组pre[i]表示原数组前 i 个元素的和那么[l, r)这个左闭右开区间的和可以用pre[r] - pre[l]一步得到。遇到连续子数组求和类问题前缀和可以把 O(n²) 的区间枚举降到 O(1) 查询如果再配合哈希表还能解决“和为 target 的连续子数组个数”这类问题典型代表是 LeetCode 560。模板代码可直接在 LeetCode 560 中提交from typing import List from collections import defaultdict class Solution: def subarraySum(self, nums: List[int], k: int) - int: pre 0 cnt defaultdict(int) cnt[0] 1 ans 0 for x in nums: pre x # 如果之前存在 pre - k意味着存在连续子数组和为 k ans cnt[pre - k] cnt[pre] 1 return ans理解这段代码的关键是“哈希表存的是前缀和出现的次数”。我们遍历数组时维护当前前缀和pre如果曾经出现过前缀和pre - k那么从那个位置之后到当前位置的这段连续子数组和就是 k。常见误区经典前缀和数组写法中pre长度是n 1下标要错开否则很容易越界。哈希表写法里的cnt[0] 1也不能漏它表示“前缀和为 0 出现了一次”对应子数组从数组开头开始的场景。典型题目LeetCode 303 区域和检索、LeetCode 560 和为 K 的子数组、LeetCode 437 路径总和 III把树路径也用前缀和思路处理。3.2 双指针有序数组与链表问题的高效解法双指针并不是某一种专属数据结构它有两种常见形态第一种是对撞指针常用于有序数组。初始化left指向开头、right指向结尾根据当前两个指针指向元素的和与 target 的大小关系决定移动哪一侧。因为数组有序指针移动方向是确定的所以不会漏解。以 LeetCode 167 两数之和 II 为例from typing import List class Solution: def twoSum(self, numbers: List[int], target: int) - List[int]: left, right 0, len(numbers) - 1 while left right: total numbers[left] numbers[right] if total target: return [left 1, right 1] if total target: left 1 else: right - 1 return [-1, -1]每次移动一个位置最多遍历完整数组一次时间复杂度 O(n)。这里能这样移动的前提是数组已经非递减排序如果数组未排序就需要先排序或改用哈希表。第二种是快慢指针。经典场景是链表快指针每次走两步慢指针每次走一步。如果链表存在环快指针一定会追上慢指针因此可以判断链表是否有环并找到环的入口。双指针模式的核心价值在于把“两两组合”的 O(n²) 暴力枚举降到 O(n)。LeetCode 15 三数之和、LeetCode 11 盛最多水的容器都是同一种思维。易错点使用对撞指针时注意别在循环内同时无脑移动两个指针。三数之和这类题目还要在获得答案后跳过重复元素否则结果会产生重复三元组。3.3 滑动窗口子串和子数组的“定长/变长”控制滑动窗口和双指针容易混淆但关注点不同。滑动窗口通常处理的是“连续子串、连续子数组满足某个条件”的问题窗口由左边界left和右边界right共同维护。右指针不断扩张把新元素纳入窗口当窗口不再满足题目要求时左指针收缩窗口直到窗口恢复合法。以 LeetCode 209 长度最小的子数组为例题目要求找出最短的连续子数组使其和大于等于 targetfrom typing import List class Solution: def minSubArrayLen(self, target: int, nums: List[int]) - int: n len(nums) left 0 total 0 ans float(inf) for right in range(n): total nums[right] while total target: ans min(ans, right - left 1) total - nums[left] left 1 return 0 if ans float(inf) else ans这段代码里for right in range(n)负责扩展窗口while total target负责判断窗口是否要收缩。每次收缩前都会尝试更新答案因为收缩后窗口不再满足条件所以合法窗口只可能在收缩前出现。易错点有的题目窗口收缩条件复杂例如 LeetCode 76 最小覆盖子串需要维护“每种字符还需要多少个”的欠账数量。如果只记住“至少包含 target 字符”这个表面条件很容易把 left 的收缩条件写错。建议把“窗口满足什么条件”单独抽成一个变量来表示例如valid或need_cnt而不是在 while 条件里临时统计。滑动窗口能够把 O(n²) 的枚举子串优化到 O(n)因为每个元素最多被 right 加入一次、被 left 移出一次。3.4 二分查找与二分答案单调性比“有序数组”更本质很多初学二分时只知道“在有序数组里查找 target”但 LeetCode 里大量题目并不是直接查找数组元素而是“搜索答案”。这类题有一个明显特征答案在一个整数区间里并且随着答案增大题目给定的判定结果呈现单调变化。先看标准二分查找模板找有序数组中第一个大于等于 target 的位置from typing import List def lower_bound(nums: List[int], target: int) - int: lo, hi 0, len(nums) while lo hi: mid (lo hi) // 2 if nums[mid] target: lo mid 1 else: hi mid return lo这段代码使用左闭右开区间循环条件是lo hi。当nums[mid] target时说明 mid 以及左侧都不可能满足因此lo mid 1否则hi mid。最终lo就是第一个满足条件的位置。二分答案的通用模板如下def can(mid) - bool: # 根据题目实现判断答案 mid 是否可行 pass lo, hi 0, max_possible_answer # 根据题目确定值域 while lo hi: mid (lo hi) // 2 if can(mid): hi mid # mid 可行尝试更小的答案 else: lo mid 1 # mid 不可行答案必须更大 return lo很多看起来完全不沾边的题都能套这个模板。例如“爱吃香蕉的狒狒”LeetCode 875虽然问的是吃香蕉速度但速度越大吃完所需时间越短满足单调性在速度区间上二分即可。具体推导会在第 5 节展开。易错点二分最容易错的是边界和死循环。统一使用“左闭右开 lo hi 更新lo mid 1或hi mid”可以避免很大一部分死循环问题。不要混用不同模板。3.5 回溯子集、组合、排列的统一解决方案回溯本质是带剪枝的深度优先搜索。很多题目要求“返回所有满足条件的方案”这类结果数量多无法用普通 DP 直接计数于是选择系统的搜索树遍历。回溯核心代码只有三步做选择、递归、撤销选择。以 LeetCode 39 组合总和为例数字可以被重复使用from typing import List class Solution: def combinationSum(self, candidates: List[int], target: int) - List[List[int]]: ans [] path [] def dfs(start: int, rest: int) - None: if rest 0: ans.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] rest: continue path.append(candidates[i]) dfs(i, rest - candidates[i]) # 允许重复所以从 i 开始 path.pop() dfs(0, target) return ans这里可以用单个start参数控制组合不允许重复的无序性。如果是求全排列每个元素只能使用一次且顺序不同算不同答案则需要用used数组标记哪些元素已经被选到当前路径中。回溯的两种形态要区分清楚组合型问题用start控制下一层只能从后面元素开始。排列型问题用used每个元素只能选一次但顺序可变。当原始数组本身包含重复数字且要求结果不能重复时先排序再在 for 循环内判断if i start and nums[i] nums[i - 1]: continue这行剪枝的含义是“同一层递归中跳过已经处理过的相同数字”。回溯复杂度通常不可接受因为它本来就是在暴力搜索全部解。真正考察的是你是否通过 sort、start、used 和可行性剪枝减少了无效路径。写递归时尽量用局部变量维护path并记得在递归返回后pop()否则结果会出现残留。3.6 动态规划状态定义比转移模板更重要动态规划是许多开发者的痛点因为它不像回溯那样有一个万能 for 循环模板。但反过来看动态规划的代码量往往很短难点集中在“状态定义”和“状态转移”上。最基础的入门模型是线性 DP。以 LeetCode 198 打家劫舍为例不能偷相邻房屋求最大金额from typing import List class Solution: def rob(self, nums: List[int]) - int: n len(nums) if n 0: return 0 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]dp[i]表示偷到第 i 间房屋时能获得的最大金额。对第 i 间房屋只有两种选择不偷则dp[i] dp[i-1]偷则第 i-1 间不能偷当前值等于dp[i-2] nums[i]。二者取最大即可。另一个高频模型是背包 DP特别是在“每个元素选或不选、计算方案数/能否组成某值”的题目中0/1 背包的一维数组模板是必须掌握的dp [0] * (capacity 1) dp[0] 1 for x in nums: for c in range(capacity, x - 1, -1): dp[c] dp[c - x] # 方案数版如果是最大价值改成 max() return dp[capacity]这里的关键点是内层循环必须倒序否则同一个元素会被重复使用变成完全背包。如果你发现“每个物品只能选一次但结果偏大”通常就是内层循环方向写反了。动态规划没有“一招鲜”的模板建议按题型积累线性 DP、背包 DP、区间 DP、状态压缩 DP。遇到新题时不要急着找模板先定义状态dp[i]