刷 LeetCode 刷到第五篇我发现自己和前几篇的状态完全不一样了。前四篇我还处于“看到题先翻题解抄完代码找手感”的阶段到了这一篇我逐渐养成了一套自己的刷题节奏拿到题先想边界再想暴力最后再琢磨怎么优化。这篇笔记我不会按题号顺序写而是按“本周我真正搞懂的算法专题”来整理——滑动窗口、动态规划、区间合并、一题多解的完整复盘以及我在刷题过程中踩过的一些坑。不管你是刚开始刷 LeetCode 的新手还是刷了几十题想进阶的开发者这篇笔记应该都能给到你一些可复用的思路而不是又一份题解搬运。1. 内容整体设计与选题拆解1.1 为什么算法笔记写到第五篇我调整了记录方式前几篇的笔记我基本上是“今天刷了哪几题、每题的题解是什么”这样平铺直叙。写到第五篇的时候我回顾了一下发现这种记录方式有一个很致命的问题一个月后再翻笔记我根本记不住当时为什么卡住、又是怎么想通的。我记住的只有答案丢掉了思考的过程这不叫笔记这叫抄写。所以从这一篇开始我强制自己换了一种记录方式每个算法专题只写核心解法重点记录“拿到这类题我怎么识别题型”“暴力解为什么慢”“最优解是怎么一步步推出来的”。另外每一题必须补一个复杂度分析不只是背结论而是自己算一遍。这样做的目的很简单面试考的不只是你会不会做这道题而是你能不能讲清楚“为什么这么做”。笔记只有围绕这个目标来写回头复习才有价值。第五篇我给自己定了三个专题滑动窗口类、动态规划入门、区间合并类。这三个专题是面试中的高频考点而且它们有一个共同特点——题目变化多但底层套路稳定。学会一个就能套用一批题。1.2 第五篇的选题思路按专题而不是按题号很多人刷 LeetCode 喜欢按题号顺序从头刷我前几篇就是这么干的结果就是前面简单题刷到吐后面难题上来就劝退。第五篇我开始换策略按专题刷题。怎么选专题主要看两点。第一是这个专题在面试里出现的频率第二是这个专题的解法能不能迁移到其他题上。滑动窗口、双指针、动态规划、区间合并都属于这种高性价比专题——看起来是某几道题但理解了核心之后起码能解决几十道同类型的变体题。具体到这一篇我挑选的题目组合是这样的专题代表题核心考点滑动窗口无重复字符的最长子串窗口收缩时机动态规划打家劫舍状态定义与转移区间合并合并区间排序后的一次遍历综合应用三数之和排序双指针去重这四道题对应的难度阶梯是简单到中等从模拟思路到抽象建模。把它们串起来看你会发现有些高深的技巧其实没那么神秘就是暴力解法加了一点“聪明的剪枝”而已。后面第二、第三章我会分别拆开细讲。2. 核心算法模块从暴力到最优解的思维跳跃2.1 滑动窗口把双层循环降成单层遍历“无重复字符的最长子串”这道题题目不难理解给一个字符串找出其中不含重复字符的最长子串长度。比如abcabcbb答案是abc长度 3。很多人的第一个反应是暴力枚举所有子串逐个检查有没有重复字符。这个思路复杂度是 O(n^3)——外层枚举起点内层枚举终点再内层检查重复。字符串长一点直接超时。滑动窗口的优化思路其实来自一个非常朴素的观察当窗口扩张到某个位置时发现当前字符和窗口内已有字符重复我们不需要从头枚举只需要把窗口左边界向右挪直到重复问题解决为止。因为窗口内的每一个位置作为起点时终点不需要重新探索前面已经算过的结果可以直接复用。def length_of_longest_substring(s): window set() left 0 result 0 for right in range(len(s)): while s[right] in window: window.remove(s[left]) left 1 window.add(s[right]) result max(result, right - left 1) return result这段代码的关键点在于while循环里的操作右指针每前进一步就把重复字符左边的所有字符全部移出窗口。有人可能会问为什么用set而不是直接用一个数组记录字符最后出现的位置set更直观、可读性好缺点是移除时需要逐个操作如果追求极致性能可以用字典维护每个字符的最新下标把while循环改成直接跳到重复位置的下一位。滑动窗口类的题目真正难的不是代码实现而是判断“什么时候该收缩窗口”。这道题是出现重复就收缩有些题目是窗口大小超过阈值就收缩还有的是当前窗口不满足条件时收缩。刷题时必须把“窗口扩张条件”和“窗口收缩时机”分开写清楚混在一起容易出边界 bug。另一个容易踩的坑是result的更新位置。有的同学把result写在while收缩循环里面这样当窗口收缩时长度会被错误地记录成收缩后的长度。正确做法是只在确保当前窗口合法之后再更新最大值。提示滑动窗口类题目有一个通用的框架可以参考——right指针负责扩张left指针负责收缩更新结果永远放在窗口合法的那个时刻。把这三件事理清楚任何滑动窗口题都能套上。2.2 动态规划状态定义对了题就解了一半动态规划是很多刷题者的心魔其实入门没有想象中那么难。就拿“打家劫舍”这道题来说一排房子每个房子里有一定金额相邻两间房子不能同时偷问你最多能偷多少钱。刚看到这道题的直觉可能是隔一间偷一间那到底是偷第 1、3、5 间还是第 2、4 间呢用暴力枚举所有方案复杂度是 2 的 n 次方完全不可行。动态规划的思路是换个角度看问题假设我已经走到第 i 间房子我“偷或不偷”这个决策其实只需要关注一个问题——到第 i 间房子为止我最多能拿多少钱。定义dp[i]为前 i 间房子能偷到的最大金额。那么第 i 间房子有两种选择不偷第 i 间那么dp[i] dp[i-1]偷第 i 间那么前一间不能偷所以dp[i] dp[i-2] nums[i]。取这两种情况的较大值状态转移方程就是dp[i] max(dp[i-1], dp[i-2] nums[i])。这个方程一旦写出来代码就非常简洁了def rob(nums): prev2 0 prev1 0 for num in nums: cur max(prev1, prev2 num) prev2, prev1 prev1, cur return prev1这里我用两个变量滚动更新没有用数组因为dp[i]只依赖前两个值空间复杂度从 O(n) 降到了 O(1)。这个优化新手很容易忽略但面试时主动说出“可以用滚动变量优化空间”是一个实打实的加分项。动态规划类的题目最核心的永远是“状态定义”。状态定义错了后面的所有推导都是白费。怎么判断状态定义得对不对我的经验是把状态写出来之后问自己两个问题——当前状态能不能从之前的状态转移过来最终答案能不能从某个或多个状态中直接得到只要这两个问题都能回答“能”这题基本就拿下了。2.3 区间合并排序之后一切变得简单“合并区间”这道题给定一堆形如[start, end]的区间把有重叠的区间合并起来。比如[[1,3],[2,6],[8,10],[15,18]]合并后是[[1,6],[8,10],[15,18]]。这道题最妙的点在于如果把区间按起点排序那么能合并的区间一定在相邻位置上。这个性质极大简化了问题——你不需要两两比较所有区间只需要从左到右扫一遍边扫边合并。def merge(intervals): if not intervals: return [] intervals.sort(keylambda x: x[0]) merged [intervals[0]] for start, end in intervals[1:]: if start merged[-1][1]: merged[-1][1] max(merged[-1][1], end) else: merged.append([start, end]) return merged注意这里有个细节当新区间的起点小于等于当前合并区间终点时需要合并但新区间的终点不一定比当前终点大比如[2,4]和[3,3]合并结果还是[2,4]所以要用max取两者终点中较大的那个。这个细节如果没注意到碰到右边界缩在里面的用例就会出错。区间合并这一类题的难点不在代码而在排序之后你是否敢信任“相邻即合并”这个结论。这个结论成立的前提是排序所以写代码时一定要记得先排序而且排序的标准是左端点升序。有的变体题需要按右端点排序比如会议室类的问题那就另当别论。刷题最怕的就是套模板套错了变体。注意合并区间时merged[-1][1]的更新必须用max不能直接赋值为end。这道题我用这个经典陷阱考过不少人十个人里有三个会踩坑。3. 实操复盘一道题的完整解题过程3.1 审题与边界条件分析第三部分我想用“三数之和”这道题完整复盘一道中等题的思考过程。题目要求给一个整数数组找出所有和为 0 的三元组且不允许重复。先审题这里有几个隐藏条件需要拆出来三元组内三个元素要下标不同但题目关心的是元素值组合“不允许重复”意味着[-1,0,1]和[1,0,-1]算同一个三元组数组可能包含重复元素排序后相邻值相等的情况很常见。边界条件也要先想好数组长度小于 3 直接返回空列表数组元素全为正或全为负不可能凑出 0直接返回空列表。不考虑这两个边界条件代码也能跑但会多做无意义计算。3.2 一题三解从暴力到排序双指针暴力解法是三层循环枚举所有三元组再用一个集合去重。时间复杂度 O(n^3)在 LeetCode 的测试数据下基本不可能通过。第二步优化是“排序哈希法”先固定第一个数然后在剩余数组里用两数之和的哈希解法找目标值。时间复杂度降为 O(n^2)但哈希表在处理“去重”问题上会比较别扭需要额外设计去重逻辑。第三步是最终方案排序 双指针。固定第一个数nums[i]然后用左指针指向i1右指针指向数组末尾。当前三数之和等于 0就记录结果并移动两侧指针小于 0说明左指针的数太小左指针右移大于 0说明右指针的数太大右指针左移。def three_sum(nums): nums.sort() n len(nums) result [] for i in range(n - 2): if i 0 and nums[i] nums[i - 1]: continue left i 1 right n - 1 target -nums[i] while left right: current_sum nums[left] nums[right] if current_sum target: result.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 current_sum target: left 1 else: right - 1 return result注意两个去重的while循环一个跳过左指针的重复元素一个跳过右指针的重复元素。去重必须放在记录结果之后否则会漏掉合法的三元组。我自己就犯过这个错在指针移动前先跳过了重复元素结果把一组正确解也跳掉了。3.3 复杂度对比与面试表达三道解法的复杂度对比整理成表格解法时间复杂度空间复杂度是否可行三层暴力 集合去重O(n^3)O(n)不可行排序 哈希O(n^2)O(n)可行但去重繁琐排序 双指针O(n^2)O(1) 或 O(排序栈)最优这里空间复杂度写 O(1) 的严格说法应该讨论排序算法的栈空间但面试时你解释清楚“除了排序需要的额外空间和输出数组没有使用其他额外存储”面试官一般会点头。面试中讲这道题我的建议是按照“暴力 → 优化 → 最优”的顺序来讲不要直接抛出双指针。因为面试官想看的是你的思考过程而不是背答案。听到你说“三层循环会超时所以考虑先排序让重复元素相邻再用双指针把两层循环压成一层”这是他们最想听到的思维链条。4. 刷题路上的坑与排查技巧4.1 边界条件最隐蔽的失分点第四部分我想集中聊聊刷题过程中最容易翻车的几个地方。首先就是边界条件。边界条件出问题往往不是因为不会算法而是因为考虑不周。比如求最长不重复子串时空字符串的输入能不能返回 0只含一种字符的字符串能不能返回正确长度 1数组只有一个元素时动态规划能不能正确处理这些用例看着简单但就是最容易漏。我现在的习惯是写完代码先不着急提交花 30 秒在头脑里跑一遍空输入、单元素输入、全部相同元素输入、全部不同元素输入这四种基础用例。这四种跑通了绝大部分边界坑就避开了。还有一个很多人忽略的技巧数组题和字符串题先问自己“长度为 0”和“长度为 1”时循环体里的逻辑是否还成立。如果不成立通常就需要在开头单独加一个 if 提前返回。这属于防御式编程面试时也完全可以直接讲出来。4.2 超时不是偶然主动算复杂度我在刷题群经常看到有人问“为什么我的代码超时了”点开一看三层循环嵌套数据规模是 10 的 5 次方超时是必然的。这里的核心问题是很多人没有“在写代码之前先估一下复杂度”的习惯。拿到题先看数据规模如果n是 10^5 级别O(n^2) 的算法基本就不能用了必须在设计阶段就排除。我在第五篇刷题时给自己立了一个规矩每一题动笔编码之前先写一行注释注明目标复杂度比如“O(n)一次遍历”。如果最后代码实现达不到这个复杂度我会停下来重新想而不是将就着提交看看能不能过。这个习惯刚开始很痛苦因为会强迫自己在编码前思考。但坚持了几十题之后收益非常明显最直接的是提交通过率大幅提升不用反复等判题结果更深层的收获是你对“哪些算法适合解决哪种规模的问题”有了体感。4.3 记忆化递归的常见误区动态规划专题里我发现一个特别普遍的问题很多同学以为递归加上缓存就是动态规划但其实只是解决了重叠子问题没有理清状态转移的顺序。递归是先从上往下分解问题再用缓存合并结果真正的动态规划是从最基础的状态开始一步步推上去。拿打家劫舍举例记忆化递归确实可以做但它有两个劣势一是递归栈有上限数据规模大一点直接爆栈二是代码的可读性不如递推动态规划清晰。我的建议是动态规划的题目尽量用递推去写从底层状态开始 build而不是用递归。这不仅是性能问题更是思维方式训练的差异——递推强迫你先想清楚状态转移顺序这对解复杂动态规划题非常有帮助。错误做法错误原因正确做法写完后不跑边界用例直接提交边界条件薄弱空输入/单元素/全相同/全不同先跑一遍超时后用“加点剪枝”凑合复杂度分析不到位先定目标复杂度再编码用记忆化递归替代所有动态规划可能爆栈且思路变形优先用递推自底向上构建状态指针移动前先跳过重复元素可能漏解先记录合法结果再跳过重复元素这张表是我最近刷题踩坑的总结今天全部整理出来放在这里也算是对自己的一种提醒。5. 关于刷题节奏与个人心得这一篇我刻意没有写太多题而是把每道题都拆得比较深。原因很简单到了这个阶段我已经不太关心“今天刷了几题”这种数量指标了。真正让我觉得解题水平提升的是做题时的反应速度——看到一道题能比以前更快地判断出它属于哪类问题能用什么套路去解以及这个套路的复杂度大概是多少。关于刷题节奏我有几个真实体会想分享。第一个体会是“要有一个错题重刷机制”。我之前一直往前赶刷过的题不管当时做没做出来过了就不再管。到了做动态规划专题时发现前面滑动窗口的题目手生了。现在我每周会固定抽出一天复盘旧题只重做那周标记了“重要”或“没做出来”的题目。重做的时候不看原来的解法强制自己在白纸上重新推一遍。这个过程很扎心因为很多题第一次做出来了第二次还是不会有。但正是这份扎心让我意识到哪些知识点是真的掌握了哪些只是当时看懂了而已。第二个体会是“写笔记要把思路和自己说的话记下来”。我第五篇笔记比前四篇质量高的原因就是我每道题在写完题解后额外加了三个小问答这道题的陷阱是什么如果忘记思路我会卡在哪一步下次再遇到类似题我第一反应应该是什么别小看这三个问题它们是把题解变成长时记忆的关键。这个系列我还会继续写下去。第六篇的初步计划是深度优先搜索和广度优先搜索专题配合树的题目来刷。其实 LeetCode 刷题是一条越走越宽的路径到后面你会发现不同专题之间的边界越来越模糊一道题可以用动态规划解也可以从图论的角度理解。也许第六篇笔记我会把这些串联的感受也写进去。