★ FEATURED ARTICLE 1. 为什么第一份 wp 要选这三道题1.1 一个合格的刷题 wp 应该记录什么把刷题记录取名为 wp最早是从竞赛圈借来的习惯。wp 就是 writeup解题报告的意思。以前很多竞赛选手打比赛后会写 wp把每道题的思路、代码、卡点、赛后才想到的优化全部复盘一遍。后来我刷在线判题平台的算法题时也沿用了这个习惯每做一个专题就写一篇 wp 作为阶段性记录。很多人刷题只追求“过了就行”提交显示绿色 AC马上就划到下一题。但真正的问题在于过了不等于会了。一个题目如果三天后重新做你还是需要看题解才能下手那它本质上并没有沉淀成你的能力。wp 逼着我把做题过程中的每个“为什么”都写下来为什么第一版超时为什么这样优化是对的边界条件为什么容易漏这些追问比那一次绿色 AC 更有价值。我这份 wp 的内容结构一般固定为题目要求、我的第一版想法、卡在哪儿、正解推导、代码、复杂度分析、测试样例、一句话总结。这样一份记录哪怕三个月后回来翻也能立即还原当时的思考上下文。1.2 选题标准不是越难越好很多刚开始刷题的人有个误区觉得要挑战困难题才算进步。实际上第一周选题最该看重的是高频出现、考点单一、有清晰的优化路径。题目越基础越适合拆解“从暴力到最优”的完整过程因为背后的思维方法是可以迁移的。我选了这三道两数之和、有效括号、移动零。它们分别对应哈希表、栈、双指针三大高频模型。这三道题的官方难度都不高但提交失败次数往往非常高说明大多数人在细节上栽过跟头。正好可以用来展示一个看似简单的题从“能做出来”到“稳定做对并且讲得清”中间到底要跨过哪些坎。这三道题还有一个共同特点它们都是很多中级题的基础组件。两数之和的优化思想会延伸到三数之和、四数之和有效括号的栈模型会延伸到括号生成和最长有效括号移动零的双指针会延伸到移除元素、删除有序数组重复项。第一份 wp 把这些地基题目吃透后面刷同类题会省下大量时间。2. 两数之和从暴力解到哈希表的完整推导2.1 题目本质与第一反应题目内容很简短给定一个整数数组和一个目标值找出数组中两个数相加等于目标值的下标。假设每种输入只对应一个答案同一个元素不能重复使用。请注意这里的“下标的返回顺序”细节大多数版本要求返回的是两个下标而不要求顺序。所以先看题再编码非常重要不然你可能会在返回值顺序上做无用功。我第一反应是两层循环枚举所有组合外层固定第一个数内层找有没有第二个数。这道题数据规模小的时候完全不会超时比如数组只有几十个元素暴力代码几乎是无感通过的。但一旦数据量到万级O(n²) 的平方级枚举就会明显变慢。这也是为什么需要“先暴力后优化”而不是一上来就写最优解暴力解是正确性基线只有先保证思路是对的优化后才不会把方向带偏。2.2 暴力解法先写对再谈快暴力解法写起来非常直白def two_sum(nums, target): n len(nums) for i in range(n): for j in range(i 1, n): if nums[i] nums[j] target: return [i, j] return []这里有两个容易翻车的点。第一内层循环从i 1开始而不是从 0 开始。如果从 0 开始就会出现同一个元素被用两次的情况比如nums [3, 3]target 6结果会返回[0, 0]这是明显错误的。第二i和j不能取同一个下标所以range(i 1, n)这个写法本质上就是在声明“当前元素不和自己匹配”把约束直接写进了循环结构里。暴力解的时间复杂度是 O(n²)空间复杂度是 O(1)。在数据量小的时候它没有任何毛病。但你得意识到内层循环干的事情本质是一次“在剩余数组中查找某个值”的操作。而“查找”这件事恰好是可以用哈希表优化的。2.3 用哈希表把 O(n²) 降到 O(n) 的关键跳跃我们先重新描述问题对于当前元素nums[i]我们需要在已经扫描过的位置里找到有没有值为target - nums[i]的元素。注意这里说的是“已经扫描过的位置”而不是“剩余位置”。用已经出现过的元素做匹配天然规避了同一元素使用两次的问题。哈希表之所以能加速是因为它把“查找某个值是否存在”的耗时从 O(n) 降到了平均 O(1)。我们要存的键值对是数值 - 下标。每遍历到一个新元素先去哈希表里查target - nums[i]查到了就直接返回答案查不到就把当前元素存进表里继续往前走。代码实现如下def two_sum(nums, target): seen {} for i, num in enumerate(nums): need target - num if need in seen: return [seen[need], i] seen[num] i return []这里有一个顺序问题值得单独强调先查询再插入。如果先插入再查询拿nums [3, 3]举例遍历到第二个 3 时哈希表里已经有了第一个 3target - num 3就会命中刚插入的当前元素返回[1, 1]。这就是同一个元素被用两次的典型错误。先查询后插入就保证匹配到的永远是之前出现过的下标。时间复杂度从 O(n²) 降到 O(n)空间复杂度升到 O(n)。这本质上是用空间换时间多维护一张哈希表换取一次遍历完成匹配。2.4 这道题最容易忽略的两个边界细节第一个是负数。很多人只盯着正数组合但实际上数组里完全可能有负数比如nums [-1, 0, 1]target 0。哈希表方案对负数天然友好因为need target - num的运算和正负无关这是它比“双指针排序”方案在处理数值正负时更省心的原因之一。第二个是目标值相同时两个数本身相等。比如nums [1, 2, 3, 3]target 6。如果把“同一个元素不能使用两次”理解成“两个相同的数不能用两次”那就错了。这里两个下标分别是 2 和 3虽然数值相等但是是不同的元素完全合法。用哈希表时seen里存的是 2遍历到 3 时need 3查到下标 2返回[2, 3]不会出问题。还有一个小忠告如果题目改成了“返回两个数本身而不是下标”那么最稳妥的方案反而可能是先排序再用左右双指针或者直接用哈希表收集数值。一旦涉及返回下标排序就会打乱原始索引所以哈希表通常是更直接的解法。3. 有效括号用栈匹配更要处理匹配之外的场景3.1 为什么括号匹配天生适合栈题目要求判断一个只包含()、[]、{}的字符串是否有效。有效定义有三条左括号必须用相同类型的右括号闭合左括号必须以正确的顺序闭合每个右括号都有一个对应的左括号。也就是说([)]这种交叉匹配是不合法的([])这种嵌套是合法的。我第一次做这道题时的第一反应是计数数一下左右括号数量是否相等。但这个方案立即被([)]否掉了因为它的左右括号数量相等却不符合正确顺序。计数只关注了“数量”完全没有关注“顺序”。括号的本质是最近匹配一个右括号应该去匹配“离它最近的、还没有被匹配掉的”左括号。这和栈的后进先出特性完全一致。你可以把一个嵌套的括号串想象成叠盘子最晚放上去的左括号是最早需要被右括号取下来匹配的。所以根本数据结构就是栈一个支持末尾追加和末尾弹出的线性结构。3.2 编码前的两个决策映射表 vs 条件判断很多新手写这道题时会写一堆if判断遇到)就看栈顶是不是(遇到]就看栈顶是不是[……代码很快膨胀还容易在括号类型较多时漏掉分支。更合理的做法是先用一个字典把匹配关系定义好。我习惯把右括号作为键、左括号作为值pairs { ): (, ]: [, }: { }这样编码逻辑就统一了遇到左括号入栈遇到右括号时检查栈顶元素是否等于pairs[char]。等于就弹出不等于就说明类型不匹配直接返回 False。用映射表的好处是逻辑单一不管遇到哪种右括号走的都是同一条判断路径减少出错可能。3.3 常规流程与几种“看似对但会挂”的输入完整代码如下def is_valid(s: str) - bool: pairs { ): (, ]: [, }: { } stack [] for ch in s: if ch in pairs: if not stack or stack[-1] ! pairs[ch]: return False stack.pop() else: stack.append(ch) return not stack遍历完之后为什么还要检查not stack因为这三种输入会让你的栈不为空(、((、([]。它们都只有左括号或者左括号比右括号多遍历结束后残留了左括号说明括号没有完全闭合必须返回 False。那几种看似对但会挂的输入主要有三类。第一类是空字符串按定义是有效的因为没有未匹配的括号。return not stack对空字符串返回 True天然正确。第二类只有右括号比如)遍历时栈为空not stack判断为真直接返回 False不会出现stack[-1]访问空栈的运行时错误。第三类是交叉匹配([)]走到)时栈顶是[和(不相等返回 False完美命中“正确顺序”约束。关于 Python 负数索引stack[-1]在栈为空时会抛出异常所以not stack or这个短路判断必须写在前面。我见过不少人在这个细节上翻车只检查了stack[-1] ! pairs[ch]却漏了栈已经为空的情况。时间复杂度是 O(n)空间复杂度是 O(n)。这道题考的不只是栈的使用更是“用数据结构去表达顺序规则”的思维所以它才会高频出现在各类技术面试的入门题里。3.4 复杂度与扩展思考很多人在面试时会被追问如果字符串里还有其他字符怎么办最简单的处理是遇到非括号字符直接跳过或者直接返回 False取决于题目定义。在线判题平台的默认版本是“只包含括号字符”不用额外判断。这道题的扩展方向非常多。比如“删除字符串中的所有相邻重复项”本质上也是一个相邻消除模型可以用栈维护当前结果再比如“最长有效括号”需要用栈配合动态规划解决难度会一下子拉高不少。这也是为什么我把它选进算法 1 的 wp基础模型的熟练度决定了你能不能快速迁移到更难的问题上。4. 移动零双指针法里最容易被误解的一题4.1 题意里的三个隐藏要求题目要求把数组中的所有 0 移动到末尾同时保持非零元素的相对顺序。注意约束条件必须在原数组上操作不拷贝额外数组尽量减少操作次数。这里其实有三个隐藏要求。第一是“原地修改”意味着你不能先过滤出非零元素再组装新数组返回。第二是“保持相对顺序”意味着如果原来非零元素的顺序是 1, 2, 3那移动后还得是 1, 2, 3不能变成 3, 2, 1。第三才是真正的含义不只把零挪走还要让它们在数组末尾排列。我见过有人尝试这样解遍历数组遇到 0 就删掉并 append 到末尾。看结果似乎是对的但数组的删除操作本身是 O(n) 的每次删除都要把后面的元素整体前移。在 Python 的list里remove和pop(0)都涉及元素移动最坏情况下操作次数会接近 O(n²)完全不符合“减少操作次数”的要求。4.2 快慢指针的推演过程正确解法是双指针。我习惯把这两个指针叫做slow和fast。slow指向“下一个非零元素应该放置的位置”fast负责遍历数组。每遇到一个非零元素就把它放到slow的位置然后slow前进一位。遍历结束后slow之后的所有位置统一填零。推演一遍会更清晰。假设数组是[0, 1, 0, 3, 12]初始slow 0fast 0。fast走到索引 1 时遇到 1放到索引 0数组变成[1, 1, 0, 3, 12]slow变成 1。fast走到索引 3 时遇到 3放到索引 1数组变成[1, 3, 0, 3, 12]slow变成 2。fast走到索引 4 时遇到 12放到索引 2数组变成[1, 3, 12, 3, 12]slow变成 3。最后从索引 3 开始到末尾全部置为 0得到[1, 3, 12, 0, 0]。这个方案的时间复杂度是 O(n)空间复杂度是 O(1)。但它有个小缺点最后一步清零可能需要额外循环。如果非零元素本来就占了前半部分后半部分清零的范围会很大吗不会最多把 n 个位置处理一遍整体仍然是 O(n)。还有一种更常见的优雅写法是“交换法”当fast遇到非零元素且它和slow指向的不是同一个位置时交换两个位置的元素。这样零会随着交换被逐步推到后面而且不需要最后的置零循环。def move_zeroes(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: if fast ! slow: nums[slow], nums[fast] nums[fast], nums[slow] slow 1交换法有一个细节需要想明白为什么不会破坏非零元素的相对顺序因为slow始终指向“当前已经整理好的非零元素序列的末尾”fast发现新的非零元素后把它交换到前面它和原来slow位置的元素此时应该是 0互换。每个非零元素被处理时都保持进入序列的顺序不会出现后出现的元素跳到先出现的元素前面去。4.3 为什么无脑 sort 或 filter 会翻车有人会说我直接用sort把 0 排到最后不就行了但问题在于 Python 的sort是稳定排序如果要让非零元素保持相对顺序必须自定义一个复杂的 key处理起来很别扭而且排序的时间复杂度至少是 O(n log n)空间复杂度也可能达到 O(n)显然不是最优解。还有人说可以用filter过滤出非零元素再拼上相应数量的 0。但这就创建了新列表违反“原地操作”的约束在线判题平台会直接报错或者被判定为不符合题意。移动零这道题的意义就是让你养成“先读清楚约束再选数据结构”的习惯看到原地操作就应该立刻想到双指针这类不依赖额外空间的方案。这道题的姊妹题非常多比如“移除元素”“删除有序数组中的重复项”“压缩字符串”。它们的共同框架都是一个指针负责遍历另一个指针负责维护答案范围。把移动零吃透之后遇到这类题会轻松很多。5. 三道题串起来的通用解题框架5.1 五步走审题、暴力、优化、编码、测试刷这三道题的过程中我慢慢总结出一套做题流程现在每次遇到新题都会按这套流程走。第一步是审题把输入输出的类型、范围、约束写在草稿纸上多举几个例子尤其是边界例子。第二步是暴力先用最直白的方式实现一遍保证正确性。哪怕效率低也没关系它提供的是“标准答案”。第三步是优化找到暴力解法里最耗时的部分尝试用更合适的数据结构替换。两数之和里耗时的是查找所以引入哈希表有效括号里需要记录嵌套顺序所以引入栈移动零里需要原地整理顺序所以引入双指针。这一步最关键的地方是问自己当前算法在“重复计算”什么第四步才是编码用清晰的变量名和代码结构把优化后的思路落下来。第五步是测试除了正常用例一定要手动跑一遍空输入、单元素输入、全相同输入、极端数值输入。这套流程看着笨但能避免大多数“看起来对了、实际上换几个用例就挂”的尴尬。5.2 复杂度分析的习惯是怎么养成的做算法题不能只满足于“通过”还要养成随手估算复杂度分析的习惯。两数之和的暴力是 O(n²)哈希表优化是 O(n) 时间 O(n) 空间有效括号是 O(n) 时间 O(n) 空间移动零是 O(n) 时间 O(1) 空间。清楚说出这些指标比代码通过更能体现理解深度。我常用的分析方法是先数循环层数。一个循环基本是 O(n)嵌套两层循环大概率是 O(n²)。再看每次循环内部做了什么如果内部有一层哈希查找那它的耗时是平均 O(1)如果有一次in列表查找那是 O(n)。递归则要单独画递归树不过这三道题里没有典型递归所以暂时不展开。空间复杂度方面简单记住你额外开辟了多少存储空间就是多大的空间复杂度。哈希表存了 n 个键值对就是 O(n)栈最多存 n 个括号也是 O(n)双指针只是多用了两个变量所以是 O(1)。5.3 从“题目做对”到“能讲清楚”的差距这里要说一个很多人忽略的点刷题最终目标不是让裁判通过你的代码而是让你在面试或者技术讨论中能把自己的思路清楚地讲出来。最直接的检验方法是费曼式复述把题解讲给一个完全没做过这道题的人听看他能不能明白。我给自己定的标准是每道题要能用一两句话概括它的本质。两数之和的本质是“用哈希表记录历史数据按需查找补数”有效括号的本质是“用栈维护最近待匹配的左括号”移动零的本质是“用快慢指针维护一个已处理区间的不变量”。这三句话比贴一大段代码更能说明你真的会了。如果讲不清楚多半是在某个“为什么”上没有想透。比如两数之和为什么先查再插因为要回避当前元素自己匹配自己。比如有效括号为什么最后要检查栈是否为空因为可能只有左括号。这些追问恰恰是写 wp 时要回答的问题。6. 刷第一周最值得记住的几条经验6.1 边界输入测试清单我踩过最多次的坑几乎都集中在边界输入上。所以现在每道题提交前我都会过一遍这份清单空输入、单个元素、输入全相同、输入全为零、目标值或者数值是极端值。有效括号里的空字符串移动零里的全零数组两数之和里的负数组合都是高频出错点。把边界测试形成习惯之后你的“一次通过率”会有非常明显的提升。很多时候提交失败并不是算法思路错而是边界漏了取栈顶前没判空、循环起始位置设错、忽略负数和 0。这些错误往往只差一两行代码但代价是一轮又一轮的无意义提交。6.2 关于“看题解”的建议很多卡住的人都会纠结到底能不能看题解我认为可以看但必须讲究方式。我的规则是独立思考三十分钟如果完全没有思路再打开题解。看题解时先别看代码只看思路描述然后合上页面自己写一遍。写完再看代码对比差异。如果一开始就盯着答案抄做一百道题也不会进步。看完题解的当天晚上可以尝试把思路讲给自己听三天后重新做一遍一周后再做一遍。这三遍不是重复劳动而是刻意回忆。第一遍是理解第二遍是巩固第三遍是检验是否真正掌握。我写 wp 的时候也会专门记录“卡在哪个点最后是怎么跳出来的”方便下次复习时快速定位。6.3 刷题节奏每天一两道比周末三连刷更有效最后分享一点个人实际感受刷题最忌讳的是“激情式突击”。我曾经一个周末连刷十几道当时感觉印象很深但一周后回头做好几道连思路都接不上。反而是工作日每天只做一两道、认真写完 wp 的日子里题目记得更牢。原因其实很简单每天一两道意味着每天都有一次主动回忆和自我测试而周末突击更像是被动接收信息缺少间隔。遗忘曲线告诉我们学习后马上重复效果并不好隔几天再提取记忆印象才深刻。所以我现在宁愿每天只刷一道也要保证把这道题吃透、写出 wp。还有一条心态建议不要拿 AC 数量当唯一指标。用一道题有没有“彻底想明白”来定义进步会踏实很多。这份 wp 写到现在我最大的收获不是会了三道题而是建立了一套从审题、暴力到优化、测试的完整动作。下一份 wp 大概率会聊一个完全不同的专题但思考路径应该是一样的先讲清楚为什么再动手写代码。
阅读完成 · 觉得有帮助？
