★ FEATURED ARTICLE LeetCode热题100这个系列刷到第四篇了。说实话越往后刷我越觉得不能再按题号顺序硬推下去了而是应该把中间这段题目按常见套路重新归一下类。数组双指针、链表边界、回溯模板、区间合并这几类题在热题100里的出现密度非常高而且彼此之间有不少共通的思考方式。如果你也是把热题100当成面试准备素材来刷而不是单纯追求“刷了多少道”那这一篇里的解题思路和踩坑记录应该比单纯贴题解更有参考价值。1. 本期选题与整体思路1.1 为什么第四期要开始做“横向归类”前三篇我是按题号顺序一路往后推的前面那些题相对基础顺序刷有助于建立手感。但刷到中部之后我发现题目开始“变熟”很多题表面不一样核心套路却高度一致。比如“无重复字符的最长子串”和“最小覆盖子串”本质都是滑动窗口“三数之和”和“盛最多水的容器”都是双指针的变体。如果还按题号刷很容易刷一道忘一道没有形成知识网络。所以第四篇我开始换策略把热题100中处于中间位置的题目按“解题套路”重新分组。这篇文章就是一个阶段性的主题复盘覆盖了四组我在实际刷题中被反复折磨的题型数组与双指针、链表操作、回溯搜索、区间与动态规划。它们正好也是面试手写代码时出现频率最高的几个方向而且每一组背后都有一两个值得死磕的底层模板。1.2 这四组题型的共同特征先说共同点。大部分这类题都不会考特别复杂的算法比如红黑树、后缀数组这种偏竞赛的知识点基本不会出现。它们真正考的是三件事边界条件的把握、指针或索引的移动逻辑、以及状态回收回溯题里特别明显。换句话说不是“你知不知道这个算法”而是“你能不能把它写对、写干净、写稳”。这些题还有一个特点暴力解通常都能过小数据但数据量一大就超时。所以刷的时候一定要养成先估算复杂度的习惯。比如滑动窗口能把O(n²)降到O(n)双指针能把O(n²)降到接近O(n)但不搞清楚为什么能降面试时换个马甲题就容易懵。2. 数组与双指针三件套滑动窗口、对撞指针和去重2.1 无重复字符的最长子串滑动窗口的标准模板这道题题号很靠前属于那种看着简单、一写就错的小题。题目不复杂给定一个字符串找出其中不含重复字符的最长子串长度。我的第一反应是暴力枚举所有子串逐个检查有没有重复字符那是O(n²)在字符串长度到几万的时候就站不住了。滑动窗口的思路本质上是让窗口右边界不断前进遇到重复字符时再把左边界往右收始终保持窗口内没有重复字符。def lengthOfLongestSubstring(s: str) - int: char_index {} left 0 ans 0 for right, c in enumerate(s): if c in char_index and char_index[c] left: left char_index[c] 1 char_index[c] right ans max(ans, right - left 1) return ans这个版本里最关键的是左边界更新那两行。我最初写的时候漏了and char_index[c] left这个条件结果用示例一测没问题但跑到s abba就出错了。原因在于当右指针遍历到第二个a时char_index[a]里存的其实是更早位置的下标已经小于当前 left 了如果不加判断就会把 left 错误地回退到窗口之外的位置得到错误答案。这个问题我愿称之为“滑动窗口过期索引坑”。只要是类似的题比如最小覆盖子串、字符串排列都存在同一个隐患。写代码时最好明确一点窗口只能向右收不能回退所以更新 left 时一定要判断历史索引是否仍然在当前窗口内。2.2 盛最多水的容器为什么移动矮的那一边这道题题意也很直白数组里的每个数字代表坐标轴上的一根垂直线高度找两根线围成的容器能装多少水。最朴素的思路是所有两两组合O(n²) 过一遍但数据量大时不行。双指针的做法是从数组两端往中间逼近每次把矮的那一侧往里移动同时记录当前面积的最大值。def maxArea(height: List[int]) - int: left, right 0, len(height) - 1 ans 0 while left right: area min(height[left], height[right]) * (right - left) ans max(ans, area) if height[left] height[right]: left 1 else: right - 1 return ans很多读者第一次看到这个解法都会问凭什么移动矮的就能保证不遗漏最优解我的理解方式是这样的容器的高度由比较矮的那根线决定。如果我把高的那侧往里移宽度变小高度又不可能超过当前已经限制容量的矮边那面积只会更小所以移动高边永远不可能带来更大值。反过来移动矮边虽然宽度减小但换了新高度后有机会突破原来的容量上限这才是唯一可能变得更优的方向。至于两边高度相等时移动哪一边本质上无所谓。因为当前面积已经是这一宽度下的最大值无论移动哪一边宽都会变小后面的面积能否超过当前值取决于新的高度而新高度与选择哪一边并不产生系统性偏差随便选一个方向继续就行。2.3 三数之和排序双指针里的去重陷阱三数之和要求找三个数使得它们的和为0并且返回的三元组不能重复。这道题我给新手的建议是先排序再用一层循环固定第一个数剩下两个数用双指针在有序数组里找。排序的作用有两层一是让双指针可以按大小关系收缩二是在这个有序序列中重复元素会相邻排列方便去重。def threeSum(nums): nums.sort() res [] n len(nums) for i in range(n - 2): if nums[i] 0: break if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: total nums[i] nums[left] nums[right] if total 0: res.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 elif total 0: left 1 else: right - 1 return res我踩过的坑主要在两个地方。第一外层循环的重复判断要写成nums[i] nums[i - 1]意思是如果这个数和上一个已经处理过的数相同就直接跳过而不是判断nums[i] nums[i 1]后者会把这个数自己也算成重复导致漏解。第二在找到一组可行解之后要去掉左右两边所有重复的区间再做left 1; right - 1。如果不做这一步可能出现重复三元组比如[-1, -1, 2]被重复统计。另外顺带提醒一下排序后如果第一个数已经大于0那后面全是正数不可能凑出0可以直接结束循环。这是一个很小的剪枝但能明显减少不必要的循环次数。3. 链表操作边界条件修炼场3.1 删除链表的倒数第N个结点快慢指针的经典运用链表题不像数组题有连续下标可以直接访问很多操作必须靠指针一步步走。删除倒数第N个结点常规思路是先遍历一遍得到链表长度再走第二遍删除指定节点这样需要两趟遍历。快慢指针的思路更优雅让快指针先出发走 N 步然后快慢指针一起前进这样当快指针到达链表末尾时慢指针正好停留在待删除节点的前一个位置。这一步的妙处在于“倒数第N个”被转换成了“快指针领先N步”这个相对距离。def removeNthFromEnd(head, n): dummy ListNode(0) dummy.next head fast slow dummy for _ in range(n): fast fast.next while fast.next: fast fast.next slow slow.next slow.next slow.next.next return dummy.next这里我强烈建议不要直接操作 head而是加一个虚拟头节点。因为如果要删除的正好是原链表的第一个节点没有 dummy 的话返回头节点就会出错。加上 dummy 之后慢指针永远停在待删节点的前一个节点删除操作统一走slow.next slow.next.next不需要单独写头节点的特殊逻辑。还有一个容易搞混的细节快指针到底先走 N 步还是 N1 步。上面这个写法里快指针先走 N 步然后while fast.next判断的是快指针的下一个节点所以当循环结束时慢指针停留在待删节点前驱。如果你喜欢改成for _ in range(n 1): fast fast.next那循环条件就变成while fast:两者逻辑等价不要写混了。3.2 两两交换链表中的节点迭代法指针顺序这道题要求把相邻节点交换比如1 - 2 - 3 - 4变成2 - 1 - 4 - 3。这类题本身不难难在迭代时指针的赋值顺序非常容易乱一步写错整段代码就变成死循环或者丢节点。我的习惯是先画图再写代码。假设当前需要交换节点a和b它们的前驱是prev。要做的操作是让prev.next指向b让a.next指向b.next让b.next指向a移动prev和当前节点继续下一轮代码写出来长这样def swapPairs(head): dummy ListNode(0) dummy.next head prev dummy while prev.next and prev.next.next: a prev.next b a.next prev.next b a.next b.next b.next a prev a return dummy.next这里的核心教训是先处理不会影响后面赋值的指针关系。如果先写b.next a再写prev.next b逻辑上也没问题但如果你先动a.next b.next再试图通过b.next找原来的 next 节点就可能已经找不到了因为b.next被改过了。所以每一步都想清楚“我改这个指针会不会把后面还需要用的地址覆盖掉”。递归写法其实更好理解返回新头节点每层处理一对节点并把后面已经处理好的链表接回来。不过面试里迭代法更常见建议两种都练一下。3.3 合并K个升序链表堆解法与分治解法的取舍合并K个有序链表热题100里很有代表性的一道题。最容易想到的做法是每次从K个头节点里找最小值取下来接到结果链表中重复N次。如果每次找最小都线性扫描K个链表复杂度就是O(KN)不够好。用优先队列可以把“找最小值”降到O(log K)。Python 里直接用heapq就能实现import heapq def mergeKLists(lists): heap [] for i, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, i, node)) dummy ListNode(0) cur dummy while heap: val, i, node heapq.heappop(heap) cur.next node cur cur.next if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next注意一个细节heapq 里不能只存(node.val, node)因为当两个节点的 val 相等时Python 会尝试比较 node 对象而链表节点没实现比较运算直接报错。解决办法是往堆里存一个不会重复的索引比如(val, i, node)这样即使 val 相同索引也能区分先后。分治解法的思路是两两合并比如K个链表先分成K/2对每对合并成一个再继续两两合并。两种做法时间复杂度都是 O(N log K)但堆解法代码短、逻辑直白分治解法空间复杂度更可控。面试时我一般先写堆解法因为不容易出错然后如果面试官继续问能不能不用额外空间再切换分治思路。4. 回溯三题模板化思考4.1 全排列与组合总和画出搜索树再动手回溯题给人的第一感觉是“递归里套循环循环里再递归”很容易绕晕。但如果把搜索路径画出来思路就会清晰很多。全排列和组合总和放在一起对比最合适因为它们共用一个回溯模板区别只在去重和剪枝策略。先看全排列def permute(nums): res [] used [False] * len(nums) path [] def dfs(): if len(path) len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] True path.append(nums[i]) dfs() path.pop() used[i] False dfs() return res这里有两个必须理解的点。第一为什么res.append(path[:])不直接 append path因为 path 在后续递归中是同一个对象递归返回时会不断 pop如果不复制一份最终 res 里存的都会是同一个被改空的列表。第二为什么递归之后要立刻path.pop()和used[i] False因为这是“恢复现场”让这个位置的尝试结束后其他可能性还能正常使用同一个数组。组合总和在模板上与全排列的差别在于它允许重复使用同一个数字而且组合不强调顺序。所以递归时传入当前起始索引begin循环从begin开始而不是从0开始这样能避免出现[2,3]和[3,2]这种同组合不同顺序的情况。def combinationSum(candidates, target): res [] def dfs(begin, path, total): if total target: res.append(path[:]) return for i in range(begin, len(candidates)): if total candidates[i] target: continue path.append(candidates[i]) dfs(i, path, total candidates[i]) path.pop() dfs(0, [], 0) return res注意这里dfs(i, path, total candidates[i])传入的是i而不是i 1因为题目允许同一个数字无限次使用。如果题目改成“每个数字只能用一次”就要改成dfs(i 1, ...)并加排序去重逻辑。把这道题和它的变体放在一起看就能理解回溯题的核心差异其实集中在“下一层递归从哪里开始”和“怎么去掉重复结果”。4.2 电话号码的字母组合映射表 逐层枚举这道题属于典型的“循环嵌套递归”入门题没有剪枝压力重点是理解递归函数的参数含义。数字到字母的映射用一个字典或数组存好然后每一层递归处理一个数字依次枚举它对应的所有字母。def letterCombinations(digits): if not digits: return [] mapping { 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz } res [] def dfs(index, path): if index len(digits): res.append(.join(path)) return for ch in mapping[digits[index]]: path.append(ch) dfs(index 1, path) path.pop() dfs(0, []) return res这道题我觉得最有价值的点是让初学者理解“回溯不一定要有显式的剪枝条件它天然就是一棵有限枚举树”。递归的深度就是数字个数每层分支就是当前数字对应的字母数量。等刷到那些需要复杂剪枝的题时你再回头看这个简单模板会更容易理解哪些状态可以提前放弃。4.3 括号生成左右括号的计数剪枝括号生成要求生成所有合法的括号组合。这类题的关键在于“合法”的定义可以在生成过程中动态判断不需要生成完整后再校验。具体来说任何时候已放的左括号数量都不能小于右括号数量否则会出现)(这种非法序列同时左括号数量不能超过n右括号数量也不能超过n。def generateParenthesis(n): res [] def dfs(left, right, path): if len(path) 2 * n: res.append(.join(path)) return if left n: path.append(() dfs(left 1, right, path) path.pop() if right left: path.append()) dfs(left, right 1, path) path.pop() dfs(0, 0, []) return res这里我最想强调的就是right left这个剪枝条件。很多初学者会写right n那样生成的括号组合里会有大量非法结果然后再去过滤效率很低代码也丑。直接在生成过程中加入约束才是回溯剪枝的正确姿势。这道题和上面的电话号码、全排列放在一起练能很清楚地感受到回溯的三个基本要素选择列表、递归深度、撤销操作。5. 区间与动态规划两个容易看漏的边界5.1 合并区间sort不是随便写的合并区间这道题看起来简单但实现起来有不少人会栽在“如何判断区间重叠”上。先看标准解法def merge(intervals): intervals.sort(keylambda x: x[0]) res [] for inter in intervals: if not res or res[-1][1] inter[0]: res.append(inter) else: res[-1][1] max(res[-1][1], inter[1]) return res排序这一步是整个算法的前提。如果不先按左端点排序两个区间可能离得很远也可能前后颠倒讨论重叠关系就变得很麻烦。先排序后每个新区间只需要和已合并结果中的最后一个区间比较即可因为所有区间按左端点单调递增最后一个区间就是最可能发生重叠的区间。重叠判断的条件是res[-1][1] inter[0]意思是前一个区间的右端点严格小于当前区间左端点那就说明两个区间没有交集可以直接把新区间隔离开否则说明至少存在交集需要合并。合并有一个特别容易被忽略的坑新区间的右端点是max(res[-1][1], inter[1])而不是直接取inter[1]。我举个实际例子[1, 4]和[2, 3]是包含关系如果直接取inter[1]合并结果会变成[1, 3]明显覆盖范围变小了正确答案应该是[1, 4]。这种“包含型重叠”在题目给的测试用例里出现概率极高一定要用max。5.2 最大子数组和从动态规划到分治思路最大子数组和是一道经典动态规划题要求找到一个连续子数组使它的元素和最大。动态规划的状态定义很直观以i结尾的最大子数组和要么是当前元素本身要么是前一个位置的最大子数组和加上当前元素。def maxSubArray(nums): cur ans nums[0] for num in nums[1:]: cur max(num, cur num) ans max(ans, cur) return ans这个做法的本质是“要么从当前重新开始要么接在前面的最优子数组后面”。很多读者会问为什么不是cur num一定比num大因为当前面的累加和已经是负数时再接一个正数会把这个正数拖小比如前面累加和是-5当前元素是3-5 3 -2反而比3更小。所以每次都比较max(num, cur num)就是为了丢弃那些负资产。动态规划版本把空间优化成了O(1)这是面试时很加分的点。如果面试官追问“能不能用分治做”可以这么理解把数组分成左右两半最大和要么在左半部分要么在右半部分要么跨过中点。跨过中点的部分需要从中点向两侧扩展分别计算最大后缀和最大前缀再加起来。分治复杂度是O(n log n)虽然不如DP但思路本身是理解线段树做区间最大子段和的基础。6. 做题之外的修炼调试、复杂度与举一反三6.1 调试技巧先把边界用例跑烂刷题写代码最怕的不是思路错而是“看起来能过几个用例实际一提交就爆错”。我自己的经验是每道题至少准备五类测试数据——空输入、单元素输入、全相同元素、最大规模输入、反常规顺序输入。拿滑动窗口那道题来说空字符串、全空格字符串、全部相同字符比如aaaa都必须测一遍。链表题则要测空链表、只有一个节点的链表、删除头节点、删除尾节点这些情况。回溯题必测的目标值恰好为0、数组长度为0、所有元素和小于目标值等等。这些用例几乎能覆盖大部分边界逻辑错误养成习惯后提交一次的通过率会高很多。另外遇到index out of range别急着在代码里乱加if。先在纸上模拟一遍指针变化确认是在哪一步越界了。我看到不少初学者遇到越界就无脑if i len(nums)套一层结果逻辑越套越乱最后连自己都看不懂。6.2 复杂度习惯写完题先算时间空间我刷题时要求自己每做一步都有复杂度意识。比如看到嵌套循环先想想有没有可能优化到双指针或哈希表看到递归先想想递归深度会不会超过栈限制。这是面试里最常被追问的点也是区分“背题选手”和“真懂选手”的地方。滑动窗口的每个字符至多被左右指针各访问一次所以整体是O(n)均摊三数之和排序花费O(nlogn)后面双指针部分是O(n²)回溯题的时间复杂度则要看搜索树节点的规模比如全排列总的路径数是n!所以是O(n×n!)合并K个链表用堆复杂度是O(NlogK)N是所有节点总数。这些复杂度在解题时不用死记但每写完一版代码心里要有数。我的习惯是在代码注释里直接写清复杂度和关键思路。这样过两周回看自己的题解不用重新推一遍代码扫一眼注释就能想起来。6.3 举一反三从一个模板到一类题刷热题100最大的收获不是记住了某道题的写法而是发现很多题目背后是同一套模板。滑动窗口模板改一改就能解“最小覆盖子串”“字符串排列”“找到所有字母异位词”快慢指针改一改就能解“环形链表”“寻找重复数”回溯模板改一改就能解“子集”“组合总和II”“全排列II”。举个小例子三道回溯题全排列、组合总和、括号生成虽然题目看起来完全不一样但核心代码框架几乎相同。都是一个递归函数里面套一个循环循环里做选择、递归、撤销。区别只在于选择列表怎么定义递归参数怎么传剪枝条件怎么加。这个认知一旦建立再遇到新的回溯题你第一反应就不会是“这题我不会”而是“它应该套哪条模板需要改进什么”。热题100刷到中部正好是建立这种“题型对照感”的时候。前30题是用来熟悉基础功的到中间这批题做横向对比比单纯加题量更重要。我个人现在的做法是每做完一组题型就把这几道题的代码翻出来并排放在一起用高亮标出它们的共同结构再把差异点写成注释贴上去。这比反复刷十道同类型的题效率高得多。还有一个亲测有效的小技巧同一道题隔一周重写一遍用秒表计时。如果第二次能在十五分钟内独立写出无 bug 的版本说明这个题型已经内化成“肌肉记忆”了。如果还是卡壳就说明理解还停留在“看题解觉得简单”的层面需要回到边界条件和模板思路上重新拆。热题100这100道题想真正吃透不是刷一遍就结束的第二轮、第三轮的对比刷才是内化的关键。
阅读完成 · 觉得有帮助？
