如果算法题也有江湖地位LeetCode第26题“删除有序数组中的重复项”就是新手村门口那只人人都要打的野猪。题目标着Easy通过率却一直不算高常年徘徊在五六成——这不是因为难而是因为太多人靠肌肉记忆AC却没真正建立算法思维。今天借着“算法题-26”这个题号我把这道题从原理推导、Python实现、边界测试到面试延伸完整讲一遍。不管你是刚开始在leetcode必刷基础算法题里打转的新手还是想弄懂python算法思维题背后逻辑的进阶者这篇都应该能给你一点不一样的东西。1. 为什么说第26题是“必刷”但90%的人没真正吃透1.1 先看清题目在问什么三个容易被忽略的细节题目本身很短给你一个升序排列的数组nums要求原地删除重复出现的元素让每个元素只出现一次最后返回删除后数组的新长度额外空间必须控制在O(1)。就这么一百来个字里面藏着三个细节绝大多数人第一遍都扫过去了。第一个细节是“有序”。这个前提直接锁死了最优解的方向。正因为数组有序所有重复值都挤在一起你才可能只跟前一个值比较就判定是否重复。如果题目把“有序”两个字去掉这道题的最优解会立刻变成哈希去重复杂度也完全不是一回事。所以读题时一定把“有序”圈出来面试官后面追问“无序怎么办”也是从这里延伸的。第二个细节是“原地”。这两个字把所有“开新数组”的方案全部否决了。很多人一上来就写return len(set(nums))期望答案是4平台一报错还困惑——题目要的是修改nums本身不是让你算个数字交差。第三个细节是返回值与考核方式之间的关系。函数返回长度但判题系统会拿这个长度去截取nums的前几个元素和期望数组逐项比对。你返回5且nums前五个元素是[0,1,2,3,4]就通过数组后面残留什么完全无所谓。理解了这一层你在本地调试时就知道该打印什么了。这三个细节叠在一起已经帮你排除了哈希表、新建列表、排序搭配等一揽子方案。剩下的路其实只有一条在原数组上维护一片“已去重区间”边扫描边把不重复的值搬进这个区间。这就是双指针思路的自然源头。1.2 简单题反而最能暴露刷题质量面试现场的观察我这些年断断续续参与过不少技术面试有个现象特别有意思有的候选人在Hard题上能背出行云流水的代码但把这道Easy题稍微改一改比如“现在允许每个元素最多保留两个重复项”立刻就卡住了。不是因为他们不聪明而是因为学这道题的方式出了问题。背题的人记住了slow和fast这两个变量名记住了nums[fast] ! nums[slow]这个判断却没记住slow在每一时刻到底代表什么。慢指针是“已去重区间中最后一个不重复元素的下标”这句语义一旦模糊所有变形题都会翻车。所以我说这道“必刷题”的价值不在AC本身而在它有没有逼你把指针语义、边界条件、复杂度来源这三样东西想清楚。这三样恰恰是算法思维的地基。地基稳了后面刷什么题都轻松地基不稳刷到一百题两百题遇到没见过的新题还是会慌。1.3 “AC了”不等于“会了”一种被高估的刷题方式现在网上流行“每日一题”“打卡刷题”很多人对待leetcode必刷基础算法题的方式是刷完、看到绿色通过、截图、明天继续。第26题这种简单题五分钟AC然后就翻篇了。但我不客气地说一个月后让你在白板上重新写这道题你大概率会在某个地方卡一下要么忘了空数组要么返回值少写一个1要么一上来用while加pop。这说明什么说明当时只是“记住了解法”没有真正“理解为什么”。我自己的刷题节奏是AC之后至少再花十分钟做三件事。第一把代码逐行讲给自己听讲不顺的地方就是理解有洞的地方第二想三个测试用例空数组算一个全重复算一个第三给自己出一道变形题比如把条件改成保留两个重复项。这十分钟的收获往往会超过再刷十道新题。能把简单题讲清楚的人才是真会。第26题作为“必刷清单”的第一梯队值得你用这种慢功夫去对待。2. 自己逼出双指针从零推导这道题的标准解法给新人讲这道题的时候我从不直接甩双指针。直接甩答案就算代码看懂了也还是“知其然不知其所以然”。更好的方式是顺着约束条件一步步把方案“逼”出来。2.1 最直觉的删除写法为何不够好大多数人第一次看到这道题第一反应都是“删除重复项嘛那就遍历遇到重复就删掉”。用Python写出来大概是这样def remove_duplicates(nums): i 0 while i len(nums) - 1: if nums[i] nums[i 1]: nums.pop(i 1) else: i 1 return len(nums)功能上这段代码是对的LeetCode上也能过。但算法思维上它有两个隐患。隐患一是复杂度。Python的list在内存里是一段连续空间pop(i)要把第i个位置之后的所有元素整体往前搬单次平均是O(n)。假如数组里一多半是重复元素每删一次都要搬一次最坏情况就到了O(n²)。题目数组长度上限是3万O(n²)就是9亿次操作Python在极端数据上能靠运气过换成追求严谨的C写法也一样不体面。隐患二是泛化能力差。你把这个while循环拿给面试官说“这是双指针”显然不是然后他改口“现在允许重复两次”这个while循环改起来非常别扭。而真正值得学的解法是在复杂度和迁移能力上都站得住脚的。2.2 从O(1)空间约束反推覆盖方案回到题目的硬约束原地修改、O(1)额外空间、有序数组。第一条排除了新数组第二条排除了哈希表第三条把“需要比较的范围”压缩成了“只需要和最近一个写入值比较”。那既然不能开新数组唯一可行的动作就是“覆盖”把值往数组靠前的位置写越界的旧值就不管了。可覆盖引出一个新问题我一边往后扫描一边把发现的唯一值往前写会不会把还没扫到的新值给盖掉答案是不会关键在于快慢指针的时序关系。慢指针指向“已去重区间的末尾”快指针指向“当前探索到的位置”快指针永远不慢于慢指针。写入只会发生在慢指针的位置而那个位置早就被快指针扫描过了属于“可以安心覆盖”的旧区域。探索过的位置才允许写没探索过的位置永远先读后写读在写前面冲突就不存在。这一步推完双指针已经不是什么高超技巧了。它是在“不能开新数组”的约束下能同时保证“扫描”和“写入”互不干扰的最简结构。2.3 快慢指针的分工和唯一易错顺序把分工用一句话概括慢指针管写入快指针管探索。慢指针初始为0因为第一个元素天然不需要去重它直接把位置先占住。快指针从1开始每个位置都跟nums[slow]比一比如果相等说明又遇到一个重复项什么都不做继续往后走如果不相等说明遇到新值了先让slow往前挪一个位置再把新值写到slow指向的坑里。这里有一个顺序细节代码一不留神就写反必须先slow 1再nums[slow] nums[fast]不能反过来。反过来写成“先赋值再移动”在部分用例上碰巧结果一样但语义就变了——变成“先覆盖当前已确认的元素再移动边界”这个语义在扩展题里非常容易踩坑。所以顺序别指望死记硬背要把slow的语义固定在“最后一个不重复元素的下标”上那么这个顺序就是唯一合理的先把边界扩出去再把新值放进来。3. Python实现与常见翻车现场代码、边界、错误修正3.1 标准解法逐行拆解与另一个高扩展写法标准双指针版本带类型标注可以直接粘贴运行from typing import List def remove_duplicates(nums: List[int]) - int: # 空数组直接返回0 if not nums: return 0 slow 0 # 已去重区间最后一个元素的下标 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 # 边界先向外扩一格 nums[slow] nums[fast] # 把新值覆盖进来 return slow 1逐行看一下slow 0表示第一个元素已经确定保留for fast in range(1, len(nums))因为第0个位置已经占住探索从下标1开始比较nums[fast]和nums[slow]前者是探索到的候选值后者是已去重区间的标杆值不等就写入相等就跳过。最后返回slow 1因为slow是下标不是数量长度永远是“最后一个下标加1”。另一个写法我个人很喜欢它把视角从“两个指针比较”换成了“一个写入位”def remove_duplicates(nums: List[int]) - int: i 0 # 下一个写入位置 for x in nums: if i 0 or x ! nums[i - 1]: nums[i] x i 1 return i这里i的含义是“下一个可以写入的位置”同时也是“目前已去重区间的长度”。x是当前扫描到的值nums[i - 1]是最近一次写入的值。只要x不等于最近写入值就可以写到i这个位置。i0时直接写入处理了第一个元素。这个写法在讨论第80题时会非常有用因为它把“允许重复几个”抽象成了一个可调整的参数而不是写死成比较相邻两位。3.2 五类边界用例对照表本地调试时我建议至少跑下面这五个用例输入数组期望长度修改后数组前N位考察点[]0[]空数组分支[1]1[1]单元素循环不执行[1,1,1,1]1[1]全部重复[1,2,3,4]4[1,2,3,4]无重复每步都写入[0,0,1,1,1,2,2,3,3,4]5[0,1,2,3,4]官方示例很多人在自测时会漏掉空数组和单元素数组恰恰是这两个用例最能暴露初始值错误。假如把slow初始值误设成1单元素数组会返回2直接报错漏了空数组判断nums[0]直接IndexError。建议本地验证时连同数组前几项一起打印nums [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] length remove_duplicates(nums) print(length, nums[:length])只打印返回值是不够的因为有些错误写法能“碰巧”返回正确长度但数组内容是错的。3.3 五个最常见错误版本从错到对的完整修正错误一漏掉空数组。解法开头加if not nums: return 0。这个错最隐蔽本地测试往往从非空用例开始一提交就IndexError。错误二返回值少1。写成return slow。slow是下标数组长度等于slow 1。说直白点slow4表示最后一个元素在4号位前面还有0到4一共5个元素。返回4就少了一个。错误三用set(nums)去重后再转列表。功能上能得到正确数量但set是O(n)额外空间违背题意。答题前先看清O(1)三个字。错误四遍历时调用nums.remove(x)或nums.pop(i)。边遍历边增删索引会乱而且remove和pop都是O(n)的。双指针的核心价值就是“不增删只覆盖”。错误五指针语义混乱。比如把slow定义为“新数组长度”而不是“最后一个元素下标”然后比较时写nums[fast] ! nums[slow - 1]初始化又从1开始。这套混搭在部分用例上能过但遇到连续三个以上的重复就会出问题。提示诊断这类错误最有效的方法不是盯着代码看而是先口头回答“我的slow指针到底指向什么”。答得出来代码基本就对了答不出来改来改去都是崩。4. 从26题长出来的一组面试题一个框架吃透27、283、80第26题最值钱的地方是它有个庞大的“家族”。LeetCode上27、283、80这些题看起来名字各不相同骨子里都是同一个双指针覆盖框架。把框架抽出来就是一句话慢指针维护“符合条件的区间边界”快指针遍历满足条件就写入不满足就跳过。每道题的区别只是“条件”那几个字不同。4.1 移除元素第27题去重只是“过滤”的特例第27题给你数组nums和一个值val原地移除所有等于val的元素返回新长度。代码def remove_element(nums, val): i 0 for x in nums: if x ! val: nums[i] x i 1 return i跟第26题对比整个框架一模一样只有条件从“不等于前一个写入值”换成了“不等于val”。第26题本质是在过滤“重复值”第27题本质是在过滤“指定值”。理解了这一点这两道题的解法在你脑子里就会合并成一个而不是两条孤立的记忆。4.2 移动零第283题过滤加补位两段式处理第283题把数组里所有0移到末尾非零元素保持原顺序。从“过滤”的视角看这道题就是“把所有非零元素过滤出来放到前面然后把剩余位置全部填0”def move_zeroes(nums): i 0 for x in nums: if x ! 0: nums[i] x i 1 for j in range(i, len(nums)): nums[j] 0有些人一看到“移动”第一反应是交换写出来的代码又长又绕。其实把“移动”拆成“过滤”和“补位”两个阶段问题瞬间变简单。这也是双指针框架的好处它逼你先想清楚“什么条件算合格”再想“不合格的怎么处理”。4.3 允许保留两个重复项第80题与k个重复项的泛化第80题是第26题的高频进阶版有序数组允许每个元素最多出现两次。标准答案极短def remove_duplicates_2(nums): i 0 for x in nums: if i 2 or x ! nums[i - 2]: nums[i] x i 1 return i和26题的“写入位”写法对比改动只有两处i 0变成i 2nums[i - 1]变成nums[i - 2]。含义是前两个元素无条件写入从第三个开始只有当前值不等于倒数第二个写入值时才能写入。这样即使x等于倒数第一个写入值只要不等于倒数第二个说明最多也就两个连续重复安全。讲到这里还可以顺手给面试官展示一下“k个重复项”的泛化版本def remove_duplicates_k(nums, k): i 0 for x in nums: if i k or x ! nums[i - k]: nums[i] x i 1 return i把26题代进去k1把80题代进去k2。一条线把三道题串完你展示的就不只是会做题而是会抽象、会总结规律。这种能力恰恰是面试官在算法题环节真正想看到的。5. 我把这道题讲给面试官时用的表达框架算法题面试跟写代码是两码事。写代码只要求AC面试却要你在十分钟左右的时间里把思路、代码、验证完整地表述出来。第26题作为Easy题很多人栽在“太简单反而不知道怎么讲”。5.1 从读题到AC的五步节奏我习惯按五步走。第一步复述题目并圈关键词。“所以我需要在一个有序数组上原地去重返回新长度空间O(1)对吧”既确认了理解一致也提示面试官我注意到“有序”和“原地”两个关键约束。第二步一句话说明思路。“我打算用双指针慢指针维护已去重区间的最后一个位置快指针扫描整个数组遇到新值就往前覆盖。”第三步白板上把示例走一遍。比如[0,0,1,1,1,2,2,3,3,4]手动写出慢指针逐步移动的过程。这一步特别重要它让面试官看到你不是背答案而是真正理解指针每一步在干什么。第四步写代码。写的时候可以顺带说“注意这里是先移动slow再赋值因为slow的语义是区间最后一个下标”。第五步主动补测试用例。“空数组返回0单元素返回1全是重复值返回1官方示例返回5。”主动测边界是加分项多数候选人都是面试官提醒了才去想边界。5.2 面试官最常追问的四个问题第一个高频追问如果数组无序怎么办答案要分两层说无序时重复值不一定是相邻的想用双指针就不行了要么先排序再双指针O(nlogn)要么用哈希表记录出现过的值O(n)时间但O(n)空间。注意原题要求O(1)空间所以排序方案更贴近原题精神。第二个高频追问slow的语义到底是什么这是最核心的一问。答“已去重区间最后一个不重复元素的下标”然后解释为什么初始值是0、为什么返回slow 1。第三个高频追问for循环遍历的同时修改数组安全吗安全因为我们只做覆盖不改变数组长度。但while里用pop就不安全——pop改变了长度影响索引代价还高。这个问题其实在考察你对Python底层行为是否清楚。第四个高频追问能不能扩展成保留k个重复项这就是前面第80题的泛化答案。能接上这一问基本上这一轮就稳了。5.3 一个能快速分层候选人的面试提问如果我是面试官问完第26题之后我会追加一句话“现在的条件是允许最多k个重复你给我把代码改一下。”真正理解框架的人会把i 1改成i k、nums[i-1]改成nums[i-k]一分钟完事靠背答案的人会在原地愣半天。这个提问几乎一测一个准。所以如果你在准备面试别只刷原题要把这道题“会生长”的能力一起准备好。6. 这道题在真实业务里的身影与我的使用体会聊点题外话。有人觉得算法题刷完就忘了跟工作没关系。我不完全同意。第26题这种“原地覆盖”思想在业务代码里出现的频率其实不低只是不会有人专门给它贴个LeetCode标签。6.1 真实场景日志去重与时间序列清洗先说我遇到过的一个场景某天要对一批带时间戳的日志做清洗要求同一个来源同一秒的日志只保留第一条同时保持时间顺序。日志已经是按时间排好序的这不就是有序数组去重吗直接套双指针慢指针维护“已清洗日志”的末尾快指针扫描日志条目不同就覆盖进来。整个清洗在内存里的一个list内完成不产生中间副本。数据量百万级时O(n)时间和O(1)额外空间的优势非常明显。还有时间序列数据的对齐去重多个采集源上报的数据相同时间戳的只保留一个顺序不能乱。同样一个框架就能解。区别只在于比较条件从“值不相等”变成“时间戳不相等”。6.2 从刷题到工程哪些经验能带走哪些不能能带走的经验一个是“能覆盖就不新建”在某些内存受限的嵌入式环境里这是硬性要求另一个是把复杂操作拆成“过滤”和“补位”两个阶段这跟业务里“先清洗再回填”的处理思路一脉相承。不能硬套的教训也有工程里数组可能来自数据库或上游接口原地修改一个list调用方拿到的是同一个对象数据就被改了。业务系统里这种“隐藏的副作用”往往比性能更可怕。所以工程上用不用原地操作取决于你是否完全掌控这个数组的生命周期。就我个人而言这道题我前前后后刷了不下二十遍每一轮都有新体会。最早背答案后来理解指针再后来把它讲给新人听最后发现它在业务里真的能落地。如果你现在刚开始刷leetcode必刷基础算法题我建议把第26题当作第一道“精刷”的题别急着追求AC数量把这十几个指针的移动真正啃透后面的python算法思维题会顺畅很多。