如果你在力扣上刷过数组类的题目大概率会撞见这两道26. 删除有序数组中的重复项以及80. 删除有序数组中的重复项 II。两者几乎是所有“数组原地操作”专题的敲门砖也是力扣热题100里的熟面孔。不少同学第一次看到题目的时候觉得很简单无非就是把重复元素去掉但真上手写代码会发现边界条件特别容易翻车。这篇文章不打算只给一个答案我会把题目背后的考察点、双指针的推导过程、两题之间的联系以及我在实际刷题和面试中踩过的坑都聊一遍。这两道题适合所有处于基础巩固期的刷题人尤其是准备面试但还没系统整理过数组题型的同学。如果你能彻底吃透“删除有序数组中的重复项”这个系列后续碰到移除元素、移动零、合并有序数组等题目时思路会顺畅很多。它们表面上是两道独立的简单题但本质上都在考察同一个抽象模型如何在原地、线性的时间内按条件过滤一个有序数组。1. 题目理解与核心思路拆解1.1 两道题到底在问什么先看第26题给定一个有序数组要求原地删除重复出现的元素使得每个元素只出现一次最后返回删除后数组的新长度。注意几个关键词有序、原地、返回长度。什么叫“返回长度”就是说你不需要真的把数组清零或者砍掉尾巴只需要确保数组前若干个位置是最终想要的元素即可返回值告诉调用者有效部分有多长。第80题则是在第26题的基础上增加了一个条件每个元素最多可以保留两次。也就是说数组[1,1,1,2,2,3]处理后前五个位置应该是[1,1,2,2,3]返回值为 5。第一眼看上去只是把“去重”放宽了一点但正是这个“最多两次”让很多习惯性写相邻元素比较的人直接翻车。这类题目之所以常出现在热题100和面试题单里是因为它考察的不是某个复杂的算法而是你对数组索引、循环边界、以及“原地修改”这回事有没有真正理解。刷这道题时很多人会想到用Python的list(set(...))或者构建一个新数组但题目明确要求原地修改而且面试官真正想听的是那个O(n)时间、O(1)空间的方案。所以咱们的核心目标可以定义为用双指针将数组前段改写成目标状态并返回有效长度。1.2 为什么说这类题考的是“保留前k个”抽象模型把两道题放到一起你会发现一个更通用的规律第26题是“每个元素最多保留1个”第80题是“每个元素最多保留2个”。再往后推一步“每个元素最多保留k个”其实就是这个系列最完整的模型。为什么要把模型抽象到这一步因为在面试里直接原封不动问你80题的场景其实不算多更多时候是让你现场推导、现场改条件。比如面试官可能加一句“如果允许重复最多3次呢”你如果能告诉他“把判断中的数字改成3就行了”他会立刻知道你理解了本质而不是背答案。我习惯用两个指针来理解这个模型slow 指针表示“已处理区域的下一个写入位置”fast 指针表示“当前正在扫描的位置”。每次 fast 扫描到一个新元素你和已处理区域的“倒数第 k 个元素”比较一下如果不同说明当前元素出现的次数还没达到 k 次可以写入如果相同说明这个值在已处理区域里已经出现过 k 次了再写就会超标直接跳过。这个思路成立的前提是数组有序。正因为有序所有相同的元素都挤在一起所以不需要哈希表来记录每个值出现了多少次只需要看看当前位置附近的情况就够了。这也是为什么“有序数组”这个条件比题目本身更值得注意。2. 第26题删除所有重复项2.1 双指针写法的由来从暴力复制说起很多人第一次做26题时会下意识地创建一个新数组把不重复的元素依次放进去再拷贝回原数组。这个思路没问题空间复杂度却是O(n)。在笔试题里也许能过但面试时就显得不够优雅了。还有一种更直觉的写法用一个count变量记录当前元素出现了几次如果次数大于1就调用nums.pop(i)删除它。这种做法在 Python 里挺常见但它有个致命问题pop操作会导致后面所有元素往前移动最坏情况下整体复杂度退化到O(n^2)。而且一边遍历一边删除索引会乱时不时就要i - 1来补偿代码写出来自己都心虚。双指针解法其实就是“复制”方案的升级版我们不创建新数组而是把原数组自身当作“目标数组”和“源数组”。fast作为源数组的读取指针负责遍历每一个元素slow作为目标数组的写入指针负责告诉fast下一个不重复的元素应该放在哪里。由于fast永远大于等于slow所以即使把某个值写到数组前面也不会覆盖掉还没扫描到的元素。这就是原地操作的合法性来源。2.2 完整代码与逐行拆解直接给标准解法Python版def remove_duplicates(nums): if not nums: return 0 slow 1 # 第一个元素必然保留所以从索引1开始 for fast in range(1, len(nums)): # 只要当前元素和前一个已保留元素不同就可以写入 if nums[fast] ! nums[slow - 1]: nums[slow] nums[fast] slow 1 return slow我把关键点拆开解释一下。第一slow为什么从 1 开始因为数组非空时第一个元素无论如何都会被保留。我们并不需要拿它和谁比较直接默认为“已处理区域”的一部分。于是slow 1表示下一个写入位置是索引1。第二for fast in range(1, len(nums))里为什么也跳过索引0因为索引0已经作为基准了我们只需要从第二个元素开始扫描。第三核心判断nums[fast] ! nums[slow - 1]。这里nums[slow - 1]是“已经保留部分的最后一个元素”。由于数组有序当前扫描到的元素如果和它不同就说明当前元素是新值若相同说明当前元素已经在保留区里出现过了直接跳过。举个例子nums [1,1,2]。初始化slow 1fast 1。fast1时nums[1]1nums[slow-1]nums[0]1相等跳过。fast2时nums[2]2nums[0]1不同那么 nums[1] 2slow变成2。遍历结束返回 slow 2数组前两位为 [1,2]符合预期。如果你把代码改成从slow 0开始然后比较nums[fast] ! nums[slow]在[1,1,2]上也碰巧能跑通但遇到[1,2,2,3]就会有问题。因为slow指向的是已经写入的位置而不是“最后一个已保留元素的位置”。具体差别在80题里会更明显我先在这里提个醒双指针的判断基准应该是“已处理区的末尾”而不是“当前写入位置”。2.3 复杂度分析和边界条件时间复杂度fast遍历数组一次循环内部每次都是常数操作所以是O(n)。空间复杂度只用了一个slow变量没有额外数组所以是O(1)。边界条件的坑主要有三个一是空数组。if not nums: return 0这行不能少否则nums[0]会越界报错。面试现场冷不丁给你一个空列表出了问题非常尴尬。二是数组长度为1。代码里slow 1fast循环范围range(1, 1)是空的直接返回1完全没问题。所以不用担心“在循环里会不会访问超出索引”的问题。三是数组内所有元素都相同比如[1,1,1,1]。每次nums[fast] ! nums[slow - 1]都不成立slow 始终是1最后返回1符合预期所有重复项只保留一个。如果数组内元素全部不同比如[1,2,3,4]那么每次判断都成立每个元素都会写入只是nums[slow] nums[fast]这一步等于自己写给自己过程无害最终返回原长度。3. 第80题最多保留两个重复项3.1 通用模板从保留1个升级到保留2个第80题刚发布时很多人沿用26题的思路改成比较nums[fast] ! nums[slow - 1]发现完全不对。比如nums [1,1,1,2,2,3]按26题思路nums[fast]和nums[slow-1]比较遇到第三个1时和上一个已保留的1相同会跳过。但实际上允许保留两个1所以第三个1才应该跳过第二个1不应该被跳过。问题出在哪因为26题“最多保留1个”时判断基准是“保留区最后一个元素”到了80题“最多保留2个”时判断基准应该变成“保留区倒数第二个元素”。你不需要关心当前元素和“保留区最后一个元素”是否相同你只需要关心“如果我把它写进去会不会导致某个值连续出现超过2次”。换句话说你应该看它和保留区倒数第2个位置的元素是否相同。于是代码几乎只改一处def remove_duplicates_ii(nums): if len(nums) 2: return len(nums) slow 2 # 前两个元素默认保留 for fast in range(2, len(nums)): # 和保留区倒数第二个元素比较 if nums[fast] ! nums[slow - 2]: nums[slow] nums[fast] slow 1 return slow你可以直接把26题的slow 1改成slow 2slow - 1改成slow - 2其他都不动。这也是我上面说“保留k个”的通用模板的来源。3.2 为什么“允许两次”不能简单用计数器有人会问那我用一个计数器记录当前连续相同元素的数量超过2个就跳过不也很快吗确实对于80题本身计数器法可行def remove_duplicates_ii_count(nums): if not nums: return 0 slow 0 count 1 for fast in range(1, len(nums)): if nums[fast] nums[slow]: count 1 if count 2: slow 1 nums[slow] nums[fast] else: count 1 slow 1 nums[slow] nums[fast] return slow 1这段代码在80题上也能通过但它的缺点是不够“通用”。如果面试官追加一句“改成最多保留3次”你得重写逻辑而不是改一个数字。相比之下nums[fast] ! nums[slow - k]的模板只需要改一两个常量面试时这种可扩展性表达要比临时想计数器逻辑显得从容得多。另外计数器法的nums[fast] nums[slow]这个比较条件也有隐患。因为slow指向当前已处理区的最后一个位置但nums[slow]的值一直是旧的当 slow 已经写入新值时条件仍成立逻辑容易绕晕。我自己初学时在这套代码里调试了很久才发现条件不统一导致的各种怪问题。3.3 测试用例与运行过程准备几个用例跑通80题的同时也验证模板输入输出长度修改后的数组前几位[]0[][1]1[1][1,1,1]2[1,1][1,1,1,2,2,3]5[1,1,2,2,3][0,0,1,1,1,1,2,3,3]7[0,0,1,1,2,3,3]以[1,1,1,2,2,3]为例手工走一遍初始slow 2nums [1,1,1,2,2,3]fast 2nums[2]1nums[slow-2]nums[0]1相等跳过fast 3nums[3]2nums[1]1不同执行 nums[2]2slow3fast 4nums[4]2nums[1]1不同执行 nums[3]2slow4fast 5nums[5]3nums[2]2不同执行 nums[4]3slow5最后数组前5位是 [1,1,2,2,3]返回5。注意此时nums[2]的值已经被覆盖成2了但我们在判断第4个元素时用的基准是slow-2 1也就是未被覆盖的旧值1所以整个判断过程不受写覆盖影响。这也是模板里使用slow - k而不是slow - 1的另一个好处你比较的永远是“保留区里足够靠前的元素”那些元素在本次扫描中不太可能被后面刚写入的值干扰。这里也建议你在本地调试时打印一下slow、fast和数组的每一轮快照很容易就能看出这个覆盖和比较过程其实非常清晰理解了就不怕代码背不熟。4. 常见错误、边界条件与排查技巧4.1 刷题时容易翻车的五个坑第一个坑也是最常见的就是把return slow 1写成return slow。在26题中如果从slow 0开始写最后返回slow 1是合理的但如果从slow 1开始返回slow即可。如果你混着写十有八九会多1或少1。最好把代码开头和返回逻辑绑定成一套不要临时改动。第二个坑忽略题目给的“有序”条件非要先把数组排序。排序会破坏原地性而且时间复杂度至少O(n log n)完全没有必要。另外如果面试题改成“无序数组去重”那题目性质就变了通常会允许哈希表不会要求原地处理。第三个坑在for fast in range(len(nums))的循环体里修改nums的长度比如用nums.pop(fast)。这样会导致循环索引错乱而且每次pop都是O(n)整体复杂度直接爆炸。我就不建议任何去重题用pop for的组合除非你明确知道数据规模非常小。第四个坑忽略空数组和长度为1的数组。很多人写完代码信心满满一提交发现[], [1]这两组用例不过立即扣分。代码开头加两行防御就好if not nums: return 0 if len(nums) 2: # 80题 return len(nums)注意26题只处理空数组就够但80题因为默认保留两个元素所以长度小于等于2时直接返回长度是最省事的。第五个坑在80题里忘记把slow 2对应的判断改成nums[slow - 2]仍用nums[slow - 1]。这种错误在编译器层面不会报错运行几个特殊用例才发现答案不对如果没测试到位就很容易漏过去。建议把26题和80题两版代码放在一起对比一眼就能发现差异。4.2 现场调试方法与测试用例清单面试时如果手写代码不确定我一般倾向于用“打印慢指针和快指针”的方式来快速验证逻辑。比如在循环里加一行print(slow, fast, nums)然后在脑子里或草稿纸上模拟一轮。你不需要真的跑代码只需要找一个代表性输入比如[1,1,1,2,2,3]手动跟踪每个变量的值变化就能确认逻辑没有偏差。这种方式比空想更容易定位问题也容易让面试官看到你的工程直觉。平时刷题时可以把下面这份用例清单保存在编辑器里提交前跑一遍# 26题用例 [] - 0 [1] - 1 [1,1,2] - 2 [1,1,1,2,3,3] - 3 [0,0,1,1,1,2,2,3,3,4] - 5 # 80题用例 [] - 0 [1] - 1 [1,1,1] - 2 [1,1,1,2,2,3] - 5 [0,0,1,1,1,1,2,3,3] - 7如果你用Python在本地写建议顺手用assert校验返回值assert remove_duplicates([0,0,1,1,1,2,2,3,3,4]) 5调试通过后再复制到力扣代码框里提交能省掉不少试错成本。4.3 面试官喜欢追问的变体问题两道题本身不难但面试官特别喜欢在这个基础上变出花样来。最常见的追问有这么几个第一“如果每个元素最多保留3次呢”这个可以直接套通用模板把slow初始值改成3比较条件改成nums[fast] ! nums[slow - 3]其他不动。前期做好准备现场能直接给出这种答法会让面试官觉得你是真懂。第二“如果数组是无序的能不能用O(1)空间去重”在无序且要求原地的情况下一般无法在O(n)时间内完成。如果面试官说允许额外空间那就用哈希表记录出现次数。这两者的区别我在扩展部分会细说。第三“如果要求删除所有重复元素只保留出现次数为1的元素呢”这其实是LeetCode的另一个经典变体比如“删除排序链表中的重复元素II”对应数组版本。此时双指针模板就不够用了因为你需要知道前一个元素的出现次数边界条件也更复杂。建议单独练一下不要和26题混在一起。第四“能不能用二分查找”有些同学看到有序数组就会条件反射地想到二分但二分适合查找单点不适合边遍历边修改。你只需要回答“这道题必须扫描一遍因为每个元素都可能是结果的一部分”就能表明你理解为什么预处理/过滤类题目不能用二分。5. 双指针技巧的延展与刷题建议5.1 同一思路在力扣其他题目中的应用“保留前k个”模型远不止26和80这两道题。力扣的27. 移除元素就是一模一样的框架给定一个值 val要求原地移除所有等于 val 的元素。用双指针写起来几乎是照搬唯一的区别是判断条件从nums[fast] ! nums[slow - k]改成nums[fast] ! val。移动零那题也可以视为同源问题把数组中所有0移动到末尾同时保持非零元素的相对顺序。用双指针扫描遇到非零元素就往前写最后把剩下的空位补零。这类题的本质都是“把符合条件的元素搬到前面去”只要掌握了 slow 和 fast 的职责划分刷起来会越来越快。还有 88. 合并两个有序数组虽然这题是逆向双指针从数组末尾开始比较写入但思维根基也是“双指针控制写入位置”。如果你把26题的 forward 方向写懂逆向版本换一下移动方向即可理解。因为你自己判断一下就会发现“力扣热题100”里很多数组题都暗藏着双指针技巧。把26题和80题作为双指针的起点性价比非常高。5.2 个人刷题顺序与复盘方法我自己的刷题顺序是先做26题再立刻做27题然后把80题当作26题的加强版来处理。这样并不是按照题目编号物理顺序而是按照难度曲线26题建立朴素的双指针思维27题把同一框架迁移到“按值过滤”80题则引入“保留数量上限”的概念迫使你重新审视比较基准。复盘时我会在笔记里记录三个东西题目的抽象模型、代码模板、以及我踩过的坑。比如“删除有序数组中的重复项”这个标题本身我在笔记里不会只写答案而是写模型有序数组原地按条件过滤模板slow初始化 fast遍历 条件比较坑slow初始值和返回值容易多180题比较基准是slow-2而不是slow-1三个月后翻看笔记几乎一眼就能唤醒当时的思路比重新刷一遍题要高效得多。另外如果你在力扣上做题建议把网页里的“执行代码”和“提交”分开看待。先多跑几个自己的测试用例再点击“提交”能减少无谓的失败次数。不过也别因为怕判错而迟迟不提交力扣判定本身很具体看它返回的输入输出往往比自己盲调更快。5.3 针对这道题最重要的几条实战体会最后说几条我在实际做题和模拟面试中最深的感受其一不要写出一个能过用例但说不清楚为什么的答案。面试官问“为什么比较 slow-1 而不是 slow”时如果你答不上来代码分数会大打折扣。你要能用一句话解释因为等于 slow-1 位置的元素已经在保留区里它表示“上一个已写入的值”而我们比较的目的是判断当前值是否和已保留的最后一个值重复。其二面试时先把边界条件说清楚再编码。比如“数组为空怎么办”“长度为1时返回1”这些并不是什么高深的点但面试官非常看重你是否习惯性地处理边界。如果你主动说“先处理空数组和长度小于2的情况”印象分会好很多。其三把这个系列的通用解法背熟几乎等于白拿一道面试题的分。因为很多公司的算法题其实就是在26题或80题上稍微变形你只要能在十分钟内写出清晰的循环已经证明了自己具备基本的数据结构和代码能力。别觉得它简单就轻视也别因为简单就跳过深入理解。如果你把26题和80题当作一个整体来学习就会发现它们并不难真正难的往往是心急时把慢指针初始值设错、返回长度不统一、或者边界没处理干净。一旦这些坑都填平以后遇到任何“有序数组原地去重”的变体你都能用同一个模板稳稳地接住。
如果你在力扣上刷过数组类的题目大概率会撞见这两道26. 删除有序数组中的重复项以及80. 删除有序数组中的重复项 II。两者几乎是所有“数组原地操作”专题的敲门砖也是力扣热题100里的熟面孔。不少同学第一次看到题目的时候觉得很简单无非就是把重复元素去掉但真上手写代码会发现边界条件特别容易翻车。这篇文章不打算只给一个答案我会把题目背后的考察点、双指针的推导过程、两题之间的联系以及我在实际刷题和面试中踩过的坑都聊一遍。这两道题适合所有处于基础巩固期的刷题人尤其是准备面试但还没系统整理过数组题型的同学。如果你能彻底吃透“删除有序数组中的重复项”这个系列后续碰到移除元素、移动零、合并有序数组等题目时思路会顺畅很多。它们表面上是两道独立的简单题但本质上都在考察同一个抽象模型如何在原地、线性的时间内按条件过滤一个有序数组。1. 题目理解与核心思路拆解1.1 两道题到底在问什么先看第26题给定一个有序数组要求原地删除重复出现的元素使得每个元素只出现一次最后返回删除后数组的新长度。注意几个关键词有序、原地、返回长度。什么叫“返回长度”就是说你不需要真的把数组清零或者砍掉尾巴只需要确保数组前若干个位置是最终想要的元素即可返回值告诉调用者有效部分有多长。第80题则是在第26题的基础上增加了一个条件每个元素最多可以保留两次。也就是说数组[1,1,1,2,2,3]处理后前五个位置应该是[1,1,2,2,3]返回值为 5。第一眼看上去只是把“去重”放宽了一点但正是这个“最多两次”让很多习惯性写相邻元素比较的人直接翻车。这类题目之所以常出现在热题100和面试题单里是因为它考察的不是某个复杂的算法而是你对数组索引、循环边界、以及“原地修改”这回事有没有真正理解。刷这道题时很多人会想到用Python的list(set(...))或者构建一个新数组但题目明确要求原地修改而且面试官真正想听的是那个O(n)时间、O(1)空间的方案。所以咱们的核心目标可以定义为用双指针将数组前段改写成目标状态并返回有效长度。1.2 为什么说这类题考的是“保留前k个”抽象模型把两道题放到一起你会发现一个更通用的规律第26题是“每个元素最多保留1个”第80题是“每个元素最多保留2个”。再往后推一步“每个元素最多保留k个”其实就是这个系列最完整的模型。为什么要把模型抽象到这一步因为在面试里直接原封不动问你80题的场景其实不算多更多时候是让你现场推导、现场改条件。比如面试官可能加一句“如果允许重复最多3次呢”你如果能告诉他“把判断中的数字改成3就行了”他会立刻知道你理解了本质而不是背答案。我习惯用两个指针来理解这个模型slow 指针表示“已处理区域的下一个写入位置”fast 指针表示“当前正在扫描的位置”。每次 fast 扫描到一个新元素你和已处理区域的“倒数第 k 个元素”比较一下如果不同说明当前元素出现的次数还没达到 k 次可以写入如果相同说明这个值在已处理区域里已经出现过 k 次了再写就会超标直接跳过。这个思路成立的前提是数组有序。正因为有序所有相同的元素都挤在一起所以不需要哈希表来记录每个值出现了多少次只需要看看当前位置附近的情况就够了。这也是为什么“有序数组”这个条件比题目本身更值得注意。2. 第26题删除所有重复项2.1 双指针写法的由来从暴力复制说起很多人第一次做26题时会下意识地创建一个新数组把不重复的元素依次放进去再拷贝回原数组。这个思路没问题空间复杂度却是O(n)。在笔试题里也许能过但面试时就显得不够优雅了。还有一种更直觉的写法用一个count变量记录当前元素出现了几次如果次数大于1就调用nums.pop(i)删除它。这种做法在 Python 里挺常见但它有个致命问题pop操作会导致后面所有元素往前移动最坏情况下整体复杂度退化到O(n^2)。而且一边遍历一边删除索引会乱时不时就要i - 1来补偿代码写出来自己都心虚。双指针解法其实就是“复制”方案的升级版我们不创建新数组而是把原数组自身当作“目标数组”和“源数组”。fast作为源数组的读取指针负责遍历每一个元素slow作为目标数组的写入指针负责告诉fast下一个不重复的元素应该放在哪里。由于fast永远大于等于slow所以即使把某个值写到数组前面也不会覆盖掉还没扫描到的元素。这就是原地操作的合法性来源。2.2 完整代码与逐行拆解直接给标准解法Python版def remove_duplicates(nums): if not nums: return 0 slow 1 # 第一个元素必然保留所以从索引1开始 for fast in range(1, len(nums)): # 只要当前元素和前一个已保留元素不同就可以写入 if nums[fast] ! nums[slow - 1]: nums[slow] nums[fast] slow 1 return slow我把关键点拆开解释一下。第一slow为什么从 1 开始因为数组非空时第一个元素无论如何都会被保留。我们并不需要拿它和谁比较直接默认为“已处理区域”的一部分。于是slow 1表示下一个写入位置是索引1。第二for fast in range(1, len(nums))里为什么也跳过索引0因为索引0已经作为基准了我们只需要从第二个元素开始扫描。第三核心判断nums[fast] ! nums[slow - 1]。这里nums[slow - 1]是“已经保留部分的最后一个元素”。由于数组有序当前扫描到的元素如果和它不同就说明当前元素是新值若相同说明当前元素已经在保留区里出现过了直接跳过。举个例子nums [1,1,2]。初始化slow 1fast 1。fast1时nums[1]1nums[slow-1]nums[0]1相等跳过。fast2时nums[2]2nums[0]1不同那么 nums[1] 2slow变成2。遍历结束返回 slow 2数组前两位为 [1,2]符合预期。如果你把代码改成从slow 0开始然后比较nums[fast] ! nums[slow]在[1,1,2]上也碰巧能跑通但遇到[1,2,2,3]就会有问题。因为slow指向的是已经写入的位置而不是“最后一个已保留元素的位置”。具体差别在80题里会更明显我先在这里提个醒双指针的判断基准应该是“已处理区的末尾”而不是“当前写入位置”。2.3 复杂度分析和边界条件时间复杂度fast遍历数组一次循环内部每次都是常数操作所以是O(n)。空间复杂度只用了一个slow变量没有额外数组所以是O(1)。边界条件的坑主要有三个一是空数组。if not nums: return 0这行不能少否则nums[0]会越界报错。面试现场冷不丁给你一个空列表出了问题非常尴尬。二是数组长度为1。代码里slow 1fast循环范围range(1, 1)是空的直接返回1完全没问题。所以不用担心“在循环里会不会访问超出索引”的问题。三是数组内所有元素都相同比如[1,1,1,1]。每次nums[fast] ! nums[slow - 1]都不成立slow 始终是1最后返回1符合预期所有重复项只保留一个。如果数组内元素全部不同比如[1,2,3,4]那么每次判断都成立每个元素都会写入只是nums[slow] nums[fast]这一步等于自己写给自己过程无害最终返回原长度。3. 第80题最多保留两个重复项3.1 通用模板从保留1个升级到保留2个第80题刚发布时很多人沿用26题的思路改成比较nums[fast] ! nums[slow - 1]发现完全不对。比如nums [1,1,1,2,2,3]按26题思路nums[fast]和nums[slow-1]比较遇到第三个1时和上一个已保留的1相同会跳过。但实际上允许保留两个1所以第三个1才应该跳过第二个1不应该被跳过。问题出在哪因为26题“最多保留1个”时判断基准是“保留区最后一个元素”到了80题“最多保留2个”时判断基准应该变成“保留区倒数第二个元素”。你不需要关心当前元素和“保留区最后一个元素”是否相同你只需要关心“如果我把它写进去会不会导致某个值连续出现超过2次”。换句话说你应该看它和保留区倒数第2个位置的元素是否相同。于是代码几乎只改一处def remove_duplicates_ii(nums): if len(nums) 2: return len(nums) slow 2 # 前两个元素默认保留 for fast in range(2, len(nums)): # 和保留区倒数第二个元素比较 if nums[fast] ! nums[slow - 2]: nums[slow] nums[fast] slow 1 return slow你可以直接把26题的slow 1改成slow 2slow - 1改成slow - 2其他都不动。这也是我上面说“保留k个”的通用模板的来源。3.2 为什么“允许两次”不能简单用计数器有人会问那我用一个计数器记录当前连续相同元素的数量超过2个就跳过不也很快吗确实对于80题本身计数器法可行def remove_duplicates_ii_count(nums): if not nums: return 0 slow 0 count 1 for fast in range(1, len(nums)): if nums[fast] nums[slow]: count 1 if count 2: slow 1 nums[slow] nums[fast] else: count 1 slow 1 nums[slow] nums[fast] return slow 1这段代码在80题上也能通过但它的缺点是不够“通用”。如果面试官追加一句“改成最多保留3次”你得重写逻辑而不是改一个数字。相比之下nums[fast] ! nums[slow - k]的模板只需要改一两个常量面试时这种可扩展性表达要比临时想计数器逻辑显得从容得多。另外计数器法的nums[fast] nums[slow]这个比较条件也有隐患。因为slow指向当前已处理区的最后一个位置但nums[slow]的值一直是旧的当 slow 已经写入新值时条件仍成立逻辑容易绕晕。我自己初学时在这套代码里调试了很久才发现条件不统一导致的各种怪问题。3.3 测试用例与运行过程准备几个用例跑通80题的同时也验证模板输入输出长度修改后的数组前几位[]0[][1]1[1][1,1,1]2[1,1][1,1,1,2,2,3]5[1,1,2,2,3][0,0,1,1,1,1,2,3,3]7[0,0,1,1,2,3,3]以[1,1,1,2,2,3]为例手工走一遍初始slow 2nums [1,1,1,2,2,3]fast 2nums[2]1nums[slow-2]nums[0]1相等跳过fast 3nums[3]2nums[1]1不同执行 nums[2]2slow3fast 4nums[4]2nums[1]1不同执行 nums[3]2slow4fast 5nums[5]3nums[2]2不同执行 nums[4]3slow5最后数组前5位是 [1,1,2,2,3]返回5。注意此时nums[2]的值已经被覆盖成2了但我们在判断第4个元素时用的基准是slow-2 1也就是未被覆盖的旧值1所以整个判断过程不受写覆盖影响。这也是模板里使用slow - k而不是slow - 1的另一个好处你比较的永远是“保留区里足够靠前的元素”那些元素在本次扫描中不太可能被后面刚写入的值干扰。这里也建议你在本地调试时打印一下slow、fast和数组的每一轮快照很容易就能看出这个覆盖和比较过程其实非常清晰理解了就不怕代码背不熟。4. 常见错误、边界条件与排查技巧4.1 刷题时容易翻车的五个坑第一个坑也是最常见的就是把return slow 1写成return slow。在26题中如果从slow 0开始写最后返回slow 1是合理的但如果从slow 1开始返回slow即可。如果你混着写十有八九会多1或少1。最好把代码开头和返回逻辑绑定成一套不要临时改动。第二个坑忽略题目给的“有序”条件非要先把数组排序。排序会破坏原地性而且时间复杂度至少O(n log n)完全没有必要。另外如果面试题改成“无序数组去重”那题目性质就变了通常会允许哈希表不会要求原地处理。第三个坑在for fast in range(len(nums))的循环体里修改nums的长度比如用nums.pop(fast)。这样会导致循环索引错乱而且每次pop都是O(n)整体复杂度直接爆炸。我就不建议任何去重题用pop for的组合除非你明确知道数据规模非常小。第四个坑忽略空数组和长度为1的数组。很多人写完代码信心满满一提交发现[], [1]这两组用例不过立即扣分。代码开头加两行防御就好if not nums: return 0 if len(nums) 2: # 80题 return len(nums)注意26题只处理空数组就够但80题因为默认保留两个元素所以长度小于等于2时直接返回长度是最省事的。第五个坑在80题里忘记把slow 2对应的判断改成nums[slow - 2]仍用nums[slow - 1]。这种错误在编译器层面不会报错运行几个特殊用例才发现答案不对如果没测试到位就很容易漏过去。建议把26题和80题两版代码放在一起对比一眼就能发现差异。4.2 现场调试方法与测试用例清单面试时如果手写代码不确定我一般倾向于用“打印慢指针和快指针”的方式来快速验证逻辑。比如在循环里加一行print(slow, fast, nums)然后在脑子里或草稿纸上模拟一轮。你不需要真的跑代码只需要找一个代表性输入比如[1,1,1,2,2,3]手动跟踪每个变量的值变化就能确认逻辑没有偏差。这种方式比空想更容易定位问题也容易让面试官看到你的工程直觉。平时刷题时可以把下面这份用例清单保存在编辑器里提交前跑一遍# 26题用例 [] - 0 [1] - 1 [1,1,2] - 2 [1,1,1,2,3,3] - 3 [0,0,1,1,1,2,2,3,3,4] - 5 # 80题用例 [] - 0 [1] - 1 [1,1,1] - 2 [1,1,1,2,2,3] - 5 [0,0,1,1,1,1,2,3,3] - 7如果你用Python在本地写建议顺手用assert校验返回值assert remove_duplicates([0,0,1,1,1,2,2,3,3,4]) 5调试通过后再复制到力扣代码框里提交能省掉不少试错成本。4.3 面试官喜欢追问的变体问题两道题本身不难但面试官特别喜欢在这个基础上变出花样来。最常见的追问有这么几个第一“如果每个元素最多保留3次呢”这个可以直接套通用模板把slow初始值改成3比较条件改成nums[fast] ! nums[slow - 3]其他不动。前期做好准备现场能直接给出这种答法会让面试官觉得你是真懂。第二“如果数组是无序的能不能用O(1)空间去重”在无序且要求原地的情况下一般无法在O(n)时间内完成。如果面试官说允许额外空间那就用哈希表记录出现次数。这两者的区别我在扩展部分会细说。第三“如果要求删除所有重复元素只保留出现次数为1的元素呢”这其实是LeetCode的另一个经典变体比如“删除排序链表中的重复元素II”对应数组版本。此时双指针模板就不够用了因为你需要知道前一个元素的出现次数边界条件也更复杂。建议单独练一下不要和26题混在一起。第四“能不能用二分查找”有些同学看到有序数组就会条件反射地想到二分但二分适合查找单点不适合边遍历边修改。你只需要回答“这道题必须扫描一遍因为每个元素都可能是结果的一部分”就能表明你理解为什么预处理/过滤类题目不能用二分。5. 双指针技巧的延展与刷题建议5.1 同一思路在力扣其他题目中的应用“保留前k个”模型远不止26和80这两道题。力扣的27. 移除元素就是一模一样的框架给定一个值 val要求原地移除所有等于 val 的元素。用双指针写起来几乎是照搬唯一的区别是判断条件从nums[fast] ! nums[slow - k]改成nums[fast] ! val。移动零那题也可以视为同源问题把数组中所有0移动到末尾同时保持非零元素的相对顺序。用双指针扫描遇到非零元素就往前写最后把剩下的空位补零。这类题的本质都是“把符合条件的元素搬到前面去”只要掌握了 slow 和 fast 的职责划分刷起来会越来越快。还有 88. 合并两个有序数组虽然这题是逆向双指针从数组末尾开始比较写入但思维根基也是“双指针控制写入位置”。如果你把26题的 forward 方向写懂逆向版本换一下移动方向即可理解。因为你自己判断一下就会发现“力扣热题100”里很多数组题都暗藏着双指针技巧。把26题和80题作为双指针的起点性价比非常高。5.2 个人刷题顺序与复盘方法我自己的刷题顺序是先做26题再立刻做27题然后把80题当作26题的加强版来处理。这样并不是按照题目编号物理顺序而是按照难度曲线26题建立朴素的双指针思维27题把同一框架迁移到“按值过滤”80题则引入“保留数量上限”的概念迫使你重新审视比较基准。复盘时我会在笔记里记录三个东西题目的抽象模型、代码模板、以及我踩过的坑。比如“删除有序数组中的重复项”这个标题本身我在笔记里不会只写答案而是写模型有序数组原地按条件过滤模板slow初始化 fast遍历 条件比较坑slow初始值和返回值容易多180题比较基准是slow-2而不是slow-1三个月后翻看笔记几乎一眼就能唤醒当时的思路比重新刷一遍题要高效得多。另外如果你在力扣上做题建议把网页里的“执行代码”和“提交”分开看待。先多跑几个自己的测试用例再点击“提交”能减少无谓的失败次数。不过也别因为怕判错而迟迟不提交力扣判定本身很具体看它返回的输入输出往往比自己盲调更快。5.3 针对这道题最重要的几条实战体会最后说几条我在实际做题和模拟面试中最深的感受其一不要写出一个能过用例但说不清楚为什么的答案。面试官问“为什么比较 slow-1 而不是 slow”时如果你答不上来代码分数会大打折扣。你要能用一句话解释因为等于 slow-1 位置的元素已经在保留区里它表示“上一个已写入的值”而我们比较的目的是判断当前值是否和已保留的最后一个值重复。其二面试时先把边界条件说清楚再编码。比如“数组为空怎么办”“长度为1时返回1”这些并不是什么高深的点但面试官非常看重你是否习惯性地处理边界。如果你主动说“先处理空数组和长度小于2的情况”印象分会好很多。其三把这个系列的通用解法背熟几乎等于白拿一道面试题的分。因为很多公司的算法题其实就是在26题或80题上稍微变形你只要能在十分钟内写出清晰的循环已经证明了自己具备基本的数据结构和代码能力。别觉得它简单就轻视也别因为简单就跳过深入理解。如果你把26题和80题当作一个整体来学习就会发现它们并不难真正难的往往是心急时把慢指针初始值设错、返回长度不统一、或者边界没处理干净。一旦这些坑都填平以后遇到任何“有序数组原地去重”的变体你都能用同一个模板稳稳地接住。
