很多人把 LeetCode Top 100 面试高频题当成一份题号索引结果刷到第 21 题才发现事情没这么简单前 20 题大多是一招鲜想到哈希表、双指针或者栈代码就出来了从第 21 题开始题目开始打组合拳链表翻转里面套递归二分查找外面包一层旋转数组回溯搜索还得处理重复结果。这篇文章聊一聊第 21 到 40 题这一档的核心解法、题目之间的关联以及面试现场容易被追问的边界细节。适合已经刷完数组、字符串、哈希表基础题正在补链表和搜索短板的读者也适合准备用一周时间集中过一遍高频区间的朋友。1. 先看清 21-40 这 20 题在考什么1.1 三种主力题型占据了大半份额这一档题目如果按考察方向分类会发现规律非常明显链表操作占了 21、23、24、25 四道回溯搜索占了 22、37、39、40 四道二分查找占了 33、34、35 三道。三个阵营加起来已经超过一半剩下的是快慢指针、模拟、滑动窗口和一道思维题。所以这个区间刷完本质上等于把链表递归、回溯剪枝、二分边界三种技能各系统练了一遍。这也是我推荐按阵营刷、而不是按题号顺序刷的原因。按题号刷容易产生一种错觉前一道是链表后一道是二分思路频繁切换其实没有形成肌肉记忆。按阵营刷同类题连续做三到五道边界条件和套路会深深刻在脑子里面试时提到“合并 K 个链表”你会下意识想到小顶堆而不是临时回忆。顺便说一下网上常见的误解Top 100 并不等于题号前 100。这个列表本身是按面试出现频率聚合的里面既有题号靠前的经典题也有题号很靠后的高频题。第 21 到 40 题这个区间虽然大部分正好对应题号顺序但更值钱的不是“序号”而是里面反复出现的考点阵营。我建议拿到任何一份高频题列表第一件事就是给你自己的薄弱题型做标记再决定先攻哪一块。1.2 真正的考察点不是“知道算法”而是边界控制这 20 道题的算法本身都不算冷门。虚拟头节点、小顶堆、lower_bound只要刷过一遍都能记住。但为什么很多人觉得这个区间比前面难因为边界情况变多了。同样是合并链表21 题要处理一条链表为空的情况24 题要处理节点为奇数时最后一对不换的情况25 题要处理剩余节点不足 K 个的情况。同样是二分33 题的等号写法不同结果完全不一样34 题一个等号写错可能死循环35 题反而最简单因为它们的模板是共通的。我甚至会建议你用下面这张表当做自测清单。每道题做对之后别急着标记完成先看表格里的“边界雷区”你能不能一眼说出答案题号题目核心考点边界雷区21合并两个有序链表虚拟头节点某条链表为空22括号生成回溯 剪枝右括号数量超过左括号23合并 K 个升序链表优先队列 / 分治堆里不能直接存节点比较24两两交换链表中的节点链表指针操作奇数长度、空链25K 个一组翻转链表递归 局部翻转剩余不足 K 个不翻转26删除有序数组中的重复项快慢指针数组为空、全是重复27移除元素快慢指针val 不存在于数组中28找出字符串中第一个匹配项的下标字符串匹配模式串比主串长29两数相除位运算INT_MIN 除以 -1 溢出30串联所有单词的子串滑动窗口单词长度乘以个数超过主串长度31下一个排列字典序规律整个数组已经是最大排列32最长有效括号栈 / 动态规划只有左括号或只有右括号33搜索旋转排序数组二分变体等号判断、只剩两个元素34在排序数组中查找目标范围二分边界模板目标不存在35搜索插入位置lower_bound目标比所有元素都大36有效的数独模拟 状态记录行列宫三条线去重37解数独回溯初始化时已填数字的剪枝38外观数列模拟 / 递归连续相同数字的计数39组合总和回溯 剪枝可无限次选取同一个数40组合总和 II回溯 同层去重结果去重条件位置写错这个表格值得你打印出来或者单独存一份。后面几个章节我会挑其中最核心的题展开讲链表四连、回溯三题、二分三题再加上一道最容易“看答案秒懂、自己做卡住”的下一个排列。2. 链表阵营虚拟头节点与递归翻转是分水岭2.1 合并两个有序链表21虚拟头节点的正确打开方式21 题是链表阵营的入门题。链表归并和数组归并最大的区别是链表没有索引退出循环后剩余那一串可以直接一次性串上而不是逐个拷贝。我见过不少人写这题时先判断 l1 和 l2 谁的值小然后手动把小的节点往后串最后还要特判“第一个节点到底是谁”。代码写出来绕来绕去面试官一看就知道没理解虚拟头节点。用 dummy 节点是最稳的写法def mergeTwoLists(l1, l2): dummy ListNode(0) tail dummy while l1 and l2: if l1.val l2.val: tail.next l1 l1 l1.next else: tail.next l2 l2 l2.next tail tail.next tail.next l1 if l1 else l2 return dummy.next为什么需要 dummy因为最终返回的链表头在循环开始前是未知的如果不用 dummy第一个节点要单独处理还要处理两条链表都为空的情况。dummy 的意思是“我先把结果串到这个假节点的后面返回时再取 dummy.next”这样第一个节点和后面的节点被一视同仁不需要特判。这题还有一个递归版本逻辑非常短def mergeTwoLists(l1, l2): if not l1: return l2 if not l2: return l1 if l1.val l2.val: l1.next mergeTwoLists(l1.next, l2) return l1 else: l2.next mergeTwoLists(l1, l2.next) return l2递归版本的思路是“每次只决定当前头节点是谁剩下的交给递归”。时间复杂度和迭代版本一样是 O(m n)。面试时可以提一句递归写法但建议用迭代版本写因为链表递归深度在极端情况下可能触发栈上限而且递归对很多人来说更容易写乱。2.2 合并 K 个升序链表23优先队列是标准答案23 题是 21 题的进阶版从两路归并变成 K 路归并。这里最自然的思路是“每轮从 K 个链表的头里挑最小的一个”但这样每轮都要扫描一次 K总复杂度会变成 O(KN)太慢。标准解法是用小顶堆优化“找最小”这一步。把所有链表的头节点放进小顶堆堆顶就是当前最小的节点弹出来串到结果尾部然后把它的 next 节点再次入堆。这样每次取最小值的代价从 O(K) 降到了 O(log K)总复杂度是 O(N log K)N 是所有节点的总数。import heapq def mergeKLists(lists): dummy ListNode(0) tail dummy heap [] for i, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, i, node)) while heap: _, i, node heapq.heappop(heap) tail.next node tail tail.next if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next这里面有一个 Python 特有的坑堆在比较元素时会从左到右比较 tuple 的每一项。如果直接存(node.val, node)当两个节点的 val 相等时Python 会尝试比较两个链表节点对象而 ListNode 之间没有定义大小比较直接报错。所以 tuple 里要加一个不会重复的索引 i保证元素可以比较。这个细节面试官不会主动考但你在白板上写代码时如果报错会非常影响状态。我个人的习惯是只要用到堆存对象一律加索引养成条件反射。另外一个思路是分治合并先两两合并再把结果继续两两合并复杂度同样是 O(N log K)。分治写起来代码要长一些但思路更“不依赖语言”。两种都值得知道面试时我推荐堆因为它短、直观、不容易写错。2.3 K 个一组翻转链表25先处理后面还是先翻转前面这题是链表阵营的 BOSS。解法有两个方向迭代和递归。迭代写起来非常容易出现指针顺序混乱我推荐优先掌握递归。递归的思路分三步先顺着链表走 K 步如果不足 K 步说明剩余段不够一组直接原样返回走满 K 步后记录 cur 为第 K1 个节点递归对 cur 做同样的处理拿到已经翻转好的后半段然后翻转当前这 K 个节点把翻转后的尾部接到后半段上。def reverseKGroup(head, k): cur head count 0 while cur and count k: cur cur.next count 1 if count k: return head new_head reverseKGroup(cur, k) prev None cur head for _ in range(k): nxt cur.next cur.next prev prev cur cur nxt head.next new_head return prev这段代码最精妙的地方是先递归处理后半段再翻转前半段。这样翻转前半段时我们不需要关心后面是什么只需要把翻转后的尾部也就是原 head指向 new_head 就行。为什么递归调用放在翻转之前因为如果先翻转前半段你会发现“后半段的头”已经不好找了你必须在翻转前先保存它。反过来先递归让 new_head 先准备好翻转完后半段的任务就只剩当前 K 个节点了逻辑清晰不容易乱。这题的边界测试用例非常多K1 时应该原样返回链表长度正好等于 K 时应该整条翻转长度是 K 的整数倍时应该全部翻转长度不能整除时剩下的尾巴保持原序。我第一次在白板上写这题时栽在了 K1 上递归打印出来发现循环里 prev 最终回到了 head但函数返回的却是翻转后的节点其实 K1 不需要任何改动。后来我会用“如果 K1 直接 return head”做短路既省时间又避免出错。24 题“两两交换链表中的节点”其实就是 K2 的特例。所以 25 题理解了24 题自然就会了。反过来如果你还不太熟 24 题建议先画图把 24 题做一遍再回来做 25 题会顺畅很多。3. 回溯阵营括号、组合总和、组合总和 II 的剪枝差异3.1 括号生成22先画选择树再写代码括号生成这题乍一看是“字符串问题”本质上是一个回溯搜索问题。每个位置有两个选择放左括号或者放右括号但选择不是任意的不然生成的序列不合法。我推荐一个稳定的写法用 left 和 right 分别表示已经使用的左括号和右括号数量。能放左括号的条件是 left n能放右括号的条件是 right left。这个条件的含义是“右括号只有在左括号比它多的时候才能放否则会产生一个无法配对的多余右括号”。def generateParenthesis(n): res [] def dfs(left, right, path): if len(path) 2 * n: res.append(path) return if left n: dfs(left 1, right, path () if right left: dfs(left, right 1, path )) dfs(0, 0, ) return res很多人纠结为什么条件写right left而不是right n。原因在于只要右括号数量还没超过左括号补右括号就是安全的而如果 right 已经等于 left说明当前序列是“平衡”的这时放右括号会立刻导致右括号多于左括号后续再怎么放左括号都无法挽救。这个判断就是这个题的剪枝核心。复杂度上生成的所有合法序列数量是第 n 个卡特兰数约等于4^n / (n * sqrt(pi * n))所以递归的节点数天然是指数级的但剪枝已经把这个搜索树压到最小了。面试时提到卡特兰数能加分但不需要背公式解释成“合法结果数量本身就是指数级”就够了。3.2 组合总和39可重复选取的“不前进”写法组合总和和括号生成的区别在于它不需要维护一个“合法性条件”而是要控制搜索顺序避免重复。39 题的设定是每个数字可以无限次使用所以递归时仍然从当前索引开始而不是从 i1 开始这样才能在同一个位置反复选同一个数字。我建议先排序再递归排序的目的有两个一是配合剪枝当 candidates[i] 已经大于剩余目标时后面的更大元素都不用看了直接 break二是让结果集里的组合以非递减顺序输出方便检查去重逻辑。def combinationSum(candidates, target): candidates.sort() res [] def dfs(start, path, remaining): if remaining 0: res.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] remaining: break path.append(candidates[i]) dfs(i, path, remaining - candidates[i]) path.pop() dfs(0, [], target) return res这里不需要显式的“去重”因为dfs(i, ...)的意思是“选完当前数之后下一个还能选它自己”而起点 start 保证了不会回头选前面的数。比如 candidates [2, 3, 6, 7]第一次选了 2之后只会从索引 0 开始继续选 2 或更大的数不会出现 [2, 3] 和 [3, 2] 同时存在的情况。剪枝的影响在实际测试中非常明显。如果不排序剩余目标小于某个值时后面依然要递归进去发现 remaining 为负再退出白白多走大量分支。排序之后一旦 candidates[i] remaining整个 for 循环直接终止。3.3 组合总和 II40去重必须发生在同一层40 题在 39 题基础上加了两条限制每个数字只能用一次结果不能有重复组合。第一条很容易递归时把dfs(i, ...)改成dfs(i 1, ...)就行。第二条是真正的难点。结果不能重复意味着输入里的相同数字不能在同一层被当作“不同的选择”。比如 candidates [1, 1, 2], target 3如果不去重你会得到两个 [1, 2]第一个用的是下标 0 的 1第二个用的是下标 1 的 1但它们作为组合是完全一样的。去重条件写成if i start and candidates[i] candidates[i - 1]: continue这个条件的位置是很多人的痛点。为什么不是i 0因为 i 是当前层循环的起点。如果写成i 0那么当 start 本身指向的是第二个重复元素时会把合法的选择也跳过。比如 candidates [1, 1, 2]start 1i 1 时candidates[1] 和 candidates[0] 相同但此时 start 就是 1这个元素是这一层允许选择的第一个元素不应该跳过跳过它会导致漏解。用一个更直白的例子理解同一层 for 循环中如果后一个数和前一个数相同那么“用后一个数”得到的所有组合都能通过“用前一个数”得到前一个数已经替它搜过了所以遇到相同值跳过即可。这就是“同一层去重”的含义。完整代码骨架def combinationSum2(candidates, target): candidates.sort() res [] def dfs(start, path, remaining): if remaining 0: res.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] remaining: break if i start and candidates[i] candidates[i - 1]: continue path.append(candidates[i]) dfs(i 1, path, remaining - candidates[i]) path.pop() dfs(0, [], target) return res这个去重模式在子集 II、全排列 II 里会反复出现。建议你把这个条件单独拿出来背下来然后自己改写到子集和全排列题里验证一遍从此不再害怕“组合去重类”的题目。4. 二分变体旋转数组搜索与左右边界查找4.1 搜索旋转排序数组33先判断哪一半有序33 题是二分法的经典变体。数组本身是升序的但在某个未知位置发生了旋转比如 [0,1,2,4,5,6,7] 变成 [4,5,6,7,0,1,2]。目标是 O(log n) 找到 target。核心洞察是二分取中点 mid 之后左右两段至少有一段是有序的。判断方法nums[left] nums[mid]如果成立说明 mid 落在左升序段否则 mid 在右段。def search(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: return mid if nums[left] nums[mid]: if nums[left] target nums[mid]: right mid - 1 else: left mid 1 else: if nums[mid] target nums[right]: left mid 1 else: right mid - 1 return -1这里最容易被忽视的是nums[left] nums[mid]这个等号。为什么必须有等号因为当区间只剩两个元素时比如[3, 1]left 和 mid 会指向同一个位置此时没有等号的话这个分支会被误判为“右段有序”导致搜索方向错误。加上等号意味着当一个元素时我们愿意把它当作左段有序来处理保住正确性。判断 target 落在哪一侧时注意闭区间范围。左段有序时target 如果满足nums[left] target nums[mid]说明在左半否则在右半右段有序时target 如果满足nums[mid] target nums[right]说明在右半否则在左半。这个范围判断的符号一定要仔细特别是开闭区间方向。4.2 找第一个和最后一个位置34两个二分模板34 题要求找一个目标值在排序数组中的第一个和最后一个下标。一条直观的方法是二分一次找到目标后向左右线性扩展但最坏情况会退化到 O(n)比如数组全是同一个值。正确做法是写两个二分分别求下界和上界。def searchRange(nums, target): def lower_bound(): left, right 0, len(nums) while left right: mid (left right) // 2 if nums[mid] target: right mid else: left mid 1 return left def upper_bound(): left, right 0, len(nums) while left right: mid (left right) // 2 if nums[mid] target: right mid else: left mid 1 return left l, r lower_bound(), upper_bound() return [l, r - 1] if l r else [-1, -1]这个模板用的是left right 左闭右开区间。注意upper_bound返回的是“第一个大于 target 的位置”不是最后一个等于 target 的位置。所以最终结果是[l, r - 1]如果 l r说明 target 不存在返回 [-1, -1]。这个模板不容易死循环的原因每次循环都会把 mid 赋给 left 或 right 的一个区间长度严格减半。当 left right 时循环结束不存在 mid 卡在原地的可能。相比之下left right的写法稍不留神就会在边界处死循环所以我个人更推荐左闭右开模板。4.3 搜索插入位置35本质就是 lower_bound35 题其实是 34 题里 lower_bound 的直接应用。题目要求如果 target 存在返回它的下标如果不存在返回插入之后它应该占的位置。这正好就是“第一个大于等于 target 的位置”的定义。def searchInsert(nums, target): left, right 0, len(nums) while left right: mid (left right) // 2 if nums[mid] target: right mid else: left mid 1 return left这个代码和上面的 lower_bound 一模一样。需要记住的是左闭右开区间里 right 初始值是 len(nums)而不是 len(nums)-1这样才能处理 target 比所有元素都大的情况——此时 left 会一路走到 len(nums)语义上正好是“插入到数组末尾”。33、34、35 三题如果连着刷你会发现它们共用同一个二分基础只是修改了条件判断。很多人觉得二分难是因为在记模板而不是在理解“区间不变量”。只要记住你维护的是一个区间这个区间内包含所有可能的目标位置每轮把区间劈成两半并排除掉绝对不可能的一侧循环结束后 left 就是答案。5. 下一个排列31一道靠反直觉规律拿分的题5.1 从例子中找到字典序规律31 题是这一区间里最像“脑筋急转弯”的题但它其实很有规律。题目要求把一个排列变成字典序意义上的下一个排列如果已经是最大排列则变回最小排列。找规律的方法就是看例子。比如[1,2,5,3,1]的下一个排列是[1,3,1,2,5]。观察一下发生了什么从右往左找找到第一个nums[i] nums[i1]的位置。这里 i 1因为 2 5。从右往左找找到第一个比 nums[i] 大的数这里是从右往左第一个大于 2 的数也就是 3。交换 nums[i] 和这个数得到 [1,3,5,2,1]。把 i1 之后的部分反转得到 [1,3,1,2,5]。为什么最后要反转因为 i 的右侧原来是降序排列也就是“当前后缀已经是最大排列”反转之后变成升序是字典序最小的后缀这样整体才是“下一个排列”。def nextPermutation(nums): n len(nums) i n - 2 while i 0 and nums[i] nums[i 1]: i - 1 if i 0: nums.reverse() return j n - 1 while nums[j] nums[i]: j - 1 nums[i], nums[j] nums[j], nums[i] nums[i 1:] reversed(nums[i 1:])第一次看这个解法的人普遍会觉得“每个步骤都懂但想不到”。没关系这题本来就是靠记忆规律得分。面试出现频率不算最高但一旦出现解法很短只要记住这个流程就能在一分钟内写完属于性价比极高的题目。5.2 两个容易忽略的测试用例这题的边界主要藏在不变量上。第一个是重复元素比如[1,5,1]。从右往左比较时nums[0] nums[1]也就是 1 5 不成立所以 i 0继续操作即可重复值不会造成麻烦但前提是代码里的比较符号必须统一用而不是。第二个是最大排列比如[3,2,1]。第一轮 while 循环会一直走到 i -1说明整个数组本身就是降序没有更大的排列直接整体反转变成[1,2,3]。如果你漏了这个判断后面访问 nums[i] 时会直接数组越界。我在面试里遇到过有人把“下一个排列”和“全排列的递归生成”搞混试图用回溯求全排列再排序搜索那样做时间复杂度和代码量都爆炸。面试官基本不会期待你用那种方式只要你能说出“字典序规律”这几个字然后背出三步流程这题就稳了。5.3 顺带把快慢指针两题也收掉这一区间里还有 26 和 27 两道快慢指针题代码量很小但同样值得注意。26 题要求原地删除有序数组中的重复项思路是慢指针指向“下一个不重复元素要写的位置”快指针遍历所有元素遇到和前一个不同的元素就写到慢指针位置。27 题移除元素更简单快指针遍历遇到不等于 val 的元素就写到慢指针位置。两题的代码结构几乎一模一样区别只在“保留条件”是“不等于前一个”还是“不等于 val”。def removeDuplicates(nums): slow 0 for fast in range(len(nums)): if nums[slow] ! nums[fast]: slow 1 nums[slow] nums[fast] return slow 1严格来说 26 题还要注意“有序”这个条件因为它是和前一个比较而不是和慢指针位置比较所以 fast 可以直接看 nums[fast] 和 nums[fast-1] 是否不同。这两题在面试里经常被当热身手撸题重点考察的是原地修改、不开额外数组能做到 O(1) 空间就是满分。剩下像 28、29、30、32、36、37、38 这些题各有各的看点。28 的 KMP 值得单独花半天学32 可以用栈也可以用动态规划是“看似简单但状态定义讲究”的好题36 有效数独用三个二维数组记录就能过37 解数独本质就是高级版回溯29 两数相除考的是位运算和溢出边界30 串联所有单词的子串是滑动窗口里的难点。这些题不需要逐一在这篇里展开但你按表刷的时候别跳过它们各自代表一种完整的小题型。6. 面试实战复盘25 题从读题到写对的全流程6.1 从面试者视角拆解思考链路与其继续讲理论不如把“K 个一组翻转链表”当成一次模拟面试完整复盘我在面试现场的思考顺序。读题的 2 分钟内要确认几件事链表节点定义是什么K 的范围是什么K 是否可能为 0 或负数题目说如果剩余节点不足 K 个就保持原样这个条件是强制的还是可选的这些点不确认清楚很容易在边界处理上返工。接下来 5 分钟画图。拿 5 个节点的链表1-2-3-4-5K2画出第一组翻转后变成2-1然后指针应该停在哪里第二组变成4-3最后剩下5不翻转整体是2-1-4-3-5。画完之后你就能直观看到翻转完一组后原链表的 head 变成了尾部它需要指向下一组的结果。画图之后思路基本已经成型递归或迭代都行。我会选择递归因为递归的代码边界更短。先写递归出口找到第 K1 个节点 cur递归处理它返回 new_head然后翻转当前 K 个节点把 head.next 接到 new_head返回翻转后的头。写代码的时间控制在 10 到 15 分钟。这题的代码只有十行左右如果你 15 分钟还没写完大概率是前面画图环节偷懒了指针关系没有提前在纸上理清。白板上直接改代码是非常痛苦的我不建议任何人跳过画图直接写。6.2 自测用例与时间分配写完代码后一定不要急着说“做完了”。主动拿测试用例在脑子里跑一遍这是面试官考察的重要环节。25 题我固定用下面几个用例自测空链表直接返回空。单节点K2不足一组原样返回。K1每组只有一个节点翻转等于没翻原样返回。K 等于链表长度整条链表翻转一次。链表长度不能被 K 整除比如 5 个节点K2最后一组只剩 1 个节点保持原序。这五个用例能覆盖绝大部分边界问题。跑第一个用例时确认递归出口能正确返回跑 K1 时确认 while 循环不会死循环跑长度不能被整除时确认最后那段没有参与翻转而是被原样接上。关于时间分配我的习惯是读题 2 分钟思路加画图 5 分钟编码 15 分钟自测 5 分钟总共控制在 25 到 30 分钟。如果一道题 20 分钟想不出思路说明这个考点的储备不够面试现场先写一个能跑的暴力解法保底再尝试优化。6.3 这一组题练到什么程度算达标按我自己的标准一组题刷完不是“做对就行”而是三天后不看题解能不能独立写对并且能脱口而出时间和空间复杂度。对 21-40 这个区间来说第 21 到 25 题不允许犹豫必须是条件反射级别的熟练第 33 到 35 题要保证二分边界一次写对22、39、40 三道回溯题要能讲清楚“为什么去重条件写在这一层”。关于复杂度也顺便给一个速查表21 是 O(mn)23 是 O(N log K)24 和 25 都是 O(n)22 是卡特兰数级别的指数39 和 40 最坏也是指数但剪枝后实用效率很高33、34、35 都是 O(log n)31 是 O(n)。面试时不要只报一个“O(n)”把其中的变量交代清楚比如 23 题的 N 是总节点数、K 是链表条数这种细节会让面试官觉得你真的理解而不是背答案。我个人的复习习惯是第一轮按阵营刷完第二轮只看表格里的“边界雷区”自测能答对就跳过答错就重新刷一遍原题。大多数人的问题不是题目做得不够多而是边界条件没有形成条件反射。这 20 道题最大的价值就在于它们把“递归边界”“二分边界”“回溯去重边界”这三类最容易翻车的边界集中在一起练完之后你会明显感觉到再遇到新的链表题和搜索题心里有底多了。