26.删除有序数组中的重复项——这道题我至少面试过别人几十次也看无数候选人在这道简单题上翻车。说它简单是因为代码最短能压到十行以内说它不简单是因为这题考察的东西其实非常底层你是否真的理解数组这个东西的本质是否真的读懂了题目的每一个字以及你的代码有没有能力处理边界情况。很多候选人上来一口气写完我说再想想他盯着代码看了三十秒突然一拍脑袋哦慢指针应该从1开始。这一拍脑袋就值一场面试的分。1. 这道题的真实分量为什么所有面试官都爱考它LeetCode第26题在题库里的标签是简单但它在面试里的出场率比其他一百道中等题加起来都高。原因很简单它的信号太丰富了。第一层信号是基础数据结构。数组是几乎所有算法题的载体但大多数人用数组的时候只停留在能用下标取值赋值这个层面并没有想过数组的两个限制长度固定、元素只能通过覆盖来删除。这道题恰好逼你在数组的这两个限制下完成操作能写出来的人至少说明对底层存储有直觉。第二层信号是双指针思想的起步点。双指针是面试最高频的解题范式之一而这道题是理解双指针最好的入门样例。很多人知道左右指针快慢指针这些名词但让他自己从零推导一遍很容易卡在为什么慢指针移动是有条件的这个点上。第三层信号是严谨性。题目里那句话不需要考虑数组中超出新长度后面的元素是新手的重灾区也是老手的送分题。你能不能把注意力放到新长度之内的元素上直接反映出你对题目细节的敏感度。所以这篇文章我打算把它拆透了讲从题目逐句分析到双指针的演进思路从代码实现到边界测试从常见错误到变体题目一次说清。尤其适合三波人看准备面试的求职者、带新人的技术导师、以及刷题刷到这道题想真正搞懂而不是背答案的人。2. 题目里的每个字都是坑逐句拆解原地删除做题最忌讳的是上来就写代码。先花三分钟把题目读透比什么都重要。我把原题逐句拆开每一句都对应一个考点。题面第一句给你一个有序数组 nums关键词是有序。有序意味着什么重复元素一定排在一起不会出现 [1, 2, 1] 这种跳着重复的情况。这是这道题能轻松解决的前提。你别小看这个前提如果你处理的是无序数组那复杂度完全不是一个量级的——要么排序要么用哈希表空间和时间都得付出代价。题面第二句请你原地删除重复出现的元素使每个元素只出现一次原地两个字是整道题的灵魂。意思是你不允许新建一个数组来存放结果只能在这个数组本身的内存空间上进行操作。为什么面试官要强调原地因为在实际生产环境里内存资源往往比我们想象的更金贵。比如你写一个数据处理中间件要对一个超大数组做去重这时候额外申请一份拷贝可能直接就把内存打爆了。原地操作是工程里实打实的需求不是刷题人自嗨。题面第三句返回删除后数组的新长度这句是这道题最巧妙的设计。数组的长度是固定的你不可能真的把一个元素从数组内存里移除你能做的只是把有效数据堆到前面然后告诉调用方从下标0到新长度减1这一截是有效数据后面的内容请你忽略。这其实就是日常开发里维护缓冲区的思路——写指针标记有效数据的边界而不是频繁地搬移内存。题面第四句不需要考虑数组中超出新长度后面的元素这句话很多人当它是废话其实它是个特权。它告诉你只要保证新长度那一截数据是正确的剩下的旧数据你爱留就留爱覆盖就覆盖没有任何人会检查。这就给用覆盖代替删除铺平了道路。我见过有人在这个约束下不敢覆盖后面元素非要搞一个临时数组再拷回来反而违反了原地的要求。把这些字全部读透解题方向其实已经出来了用两个指针一个慢指针指向已去重区域的末尾一个快指针往前探路遇到新元素就把它搬到慢指针的位置。3. 从Copy到In-Place双指针解法是怎么一步步想出来的很多人第一次做这道题直觉做法是这样的新建一个数组遍历原数组遇到不同的元素就放进去。代码写起来也简单一个循环一个判断。但问题在于这做法违反原地要求空间复杂度O(n)面试官一票就否决了。那么在原地的前提下怎么做我建议你像这样逐步推导。第一个问题我能不能做到不开新数组能因为去重这个操作本质上是把不重复的元素重新排列到数组前部。注意是重新排列而不是删除。如果你把数组想象成一条拉链重复元素是拉链上卡住的齿你要做的不是剪掉这些齿而是把拉链重新理顺让有效齿一个挨一个排在前面。第二个问题怎么在不丢失数据的前提下覆盖旧数据这就是双指针的切入点。设想你右手拿着一根指针fast往前遍历左手一根指针slow指向下一个有效位置应该放哪里。nums[fast]和nums[slow - 1]相等说明当前元素和最近保留的元素重复了跳过fast继续走。nums[fast]和nums[slow - 1]不相等说明遇到了新元素把它赋值给nums[slow]然后slow和fast一起前进。为什么是slow - 1而不是slow因为slow指的是下一个写入位置它本身还没有有效数据slow - 1才是最近一个被保留的元素。这个细节非常容易写错。第三个问题slow到底该从 0 还是 1 开始答案是 1。因为第一个元素必然被保留无论数组是什么内容下标0那个位置最终一定是有值的。把slow初始化为 1然后从fast 1开始遍历天然就跳过了对第一个元素的判断。这样写出来的代码边界最少也最好理解。如果slow从 0 开始你就必须在循环里额外处理这是第一次写入的特殊情况代码会丑很多也更容易出 bug。我把暴力解法和双指针解法放在一起对比一下维度新建数组暴力解双指针原地解空间复杂度O(n)需要额外数组O(1)只用了常数空间时间复杂度O(n)O(n)是否满足原地否是是否保留相对顺序是是对调用方友好程度返回新数组调用方要改用法只返回长度原数组前段即答案4. 代码实现与测试一次写对的完整套路思路清楚了代码就是几分钟的事。下面给两份主要语言的写法语言差异不大核心逻辑完全一致。Python 版本def removeDuplicates(nums): if not nums: return 0 slow 1 for fast in range(1, len(nums)): if nums[fast] ! nums[slow - 1]: nums[slow] nums[fast] slow 1 return slowC 版本class Solution { public: int removeDuplicates(vectorint nums) { if (nums.empty()) return 0; int slow 1; for (int fast 1; fast nums.size(); fast) { if (nums[fast] ! nums[slow - 1]) { nums[slow] nums[fast]; slow; } } return slow; } };代码一共就这几行但我建议你写完不要立刻提交先自己在脑子里跑几个用例。我把测试用例整理成一张表你可以照着自测输入期望输出处理后数组前段[]0[][1]1[1][1,1]1[1][1,1,2]2[1,2][0,0,1,1,1,2,2,3,3,4]5[0,1,2,3,4][1,2,3,4,5]无重复5[1,2,3,4,5]注意 [1,2,3,4,5] 这个用例。它没有重复元素此时每个元素都要保留slow会一路推到数组末尾循环结束时slow等于数组长度。这个用例能帮你看清楚代码在无重复情况下不会破坏原数组。还有个细节问题如果当前元素不等于前一个保留元素就往前写——那如果 fast 和 slow 刚好指向同一个位置呢比如数组没有重复元素时fast 和 slow 永远同步移动nums[slow] nums[fast]其实是自己等于自己白白做了一次赋值。性能上这点开销可以忽略不计但面试答得好不好就在这些细节里。你可以加一个判断if nums[fast] ! nums[slow - 1]: if fast ! slow: nums[slow] nums[fast] slow 1这样能避免无意义的自身赋值。虽然优化空间只有一点点但能体现出你确实思考过每个语句的开销。5. 实战中的常见错误我把别人踩过的坑都列出来这道题网上讨论量很大我甚至整理过一份错误集合几乎全是高频翻车点。错误一用nums[fast] ! nums[fast - 1]做判断这个写法单独看没错它能判断相邻两个元素是否相等。但配合slow写入时问题就出来了当 fast 已经超过 slow 一段距离nums[fast - 1]可能早就被覆盖过了。比如数组 [1,1,2,2,3]处理到 fast4值为3时nums[3] 已经被写成了2因此nums[fast - 1]的参考价值就失真了。正确做法是始终拿nums[fast]和当前已保留的最后一个元素即nums[slow - 1]比较。错误二先赋值再判断最后忘记自增有人喜欢先把nums[slow] nums[fast]放最前面然后写 if 判断什么时候该赋值结果slow和fast的步调非常容易乱。我的经验是判断要写在赋值之前只有条件成立才写写完记得slow 1这三步的顺序缺一不可。错误三返回slow 1当slow从 1 开始时它本身就代表已保留元素的数量不需要再 1。这个错误主要出在从 0 开始写但又没理清逻辑的人身上属于没想清楚slow的语义就动手了。解决方式也很简单永远按照slow 是已保留元素个数这个语义去维护它最后直接返回 slow 即可。错误四试图真正的删除重复元素用erase或remove这类操作去删元素在 vector 或 Python 的 list 里倒是行得通但时间复杂度和空间复杂度都会明显劣化。尤其 vector 的 erase 是 O(n) 的你在循环里反复 erase整体复杂度会退化到 O(n^2)。这道题要的是把有效数据前移而不是真的删除节点。错误五忽略空数组一个if not nums就能解决的问题但真有不少人会漏。空数组返回 0这个用例几乎必测丢了就是白给。6. 变体与拓展一套思路吃透所有原地去重题第26题只是一个起点。面试官太喜欢在这道题后面加一个 but 了这道题做得不错那如果允许每个元素最多出现两次呢这就引出了第80题删除有序数组中的重复项II。你把26题的思路稍微改一下就出来了def removeDuplicates(nums, k2): if len(nums) k: return len(nums) slow k for fast in range(k, len(nums)): if nums[fast] ! nums[slow - k]: nums[slow] nums[fast] slow 1 return slow把 k 当参数传进去就是最多保留 k 个重复项的通用解。第26题就是 k1 的特殊情况。看到没有只要理解了slow的语义这类题都是一套模板。这个模板还能延伸到一个更抽象的层次凡是从数组中选出一部分满足特定条件的元素保持相对顺序原地写到前段的问题都可以套快慢指针。比如移除所有等于 val 的元素第27题快指针找到一个不等于 val 的就往 slow 处写。移动零第283题快指针找到非零元素就往 slow 处写写完后剩余位置补零。排序数组的平方第977题利用有序特性用左右指针从两端往中间收。这类问题有一个共同的结构快指针负责遍历和决策慢指针负责记录下一个放哪儿。这个抽象一旦内化你以后碰到类似题目基本不用思考就能画出代码骨架。另一个值得了解的细节是这道题在实际工程里的投影随处可见。比如你在处理日志去重需要把一段日志数组中的重复条目原地规整再比如你在做数据库导入时的数据清洗要在一个巨大的缓存数组里压缩掉重复行。快慢指针这种覆盖旧数据、维护有效边界的思想其实就是这些场景里最简单高效的实现方式。7. 面试追问中的加分点从空间复杂度聊到线上一致性如果你能在写完代码后主动讲出下面这些点面试官对你的评价会明显不一样。加分点一主动说明时间空间复杂度。时间 O(n)空间 O(1)因为只用了两个索引变量没有额外数组。这句话一定要自己说不要等面试官问。加分点二解释为什么返回长度就够了。因为调用方拿到新长度后只需要遍历[0, newLength)这个区间就能拿到全部去重后的数据。这是这道题设计的巧妙之处——用长度作为通信协议避免了切片或拷贝的开销。加分点三提到值覆盖不会影响后续判断。很多人担心nums[slow] nums[fast]之后会不会把还没遍历到的数据给覆盖掉了。其实不会因为 slow 永远小于等于 fastnums[slow]所在的位置一定是已经被 fast 遍历过的位置它的旧值已经没有任何保留价值了。这一点想清楚代码的正确性就有了理论保障。加分点四从容应对变体题。上面提到的 k 模板如果你能现场写出来哪怕是伪代码都足够证明你不是背题而是真的理解了这个模型。关于线上一致性的联想算是一个工程师思维的加分点。如果这个数组不是存在内存里而是存在数据库中我们要做去重就不能只返回一个长度了事还得真正地删除数据来保证存储一致。这就是为什么这道题强调原地的工程意义——内存数组的删除成本太高用覆盖是更聪明的选择。8. 我的实测心得这个解法在真实刷题网站上的表现我自己拿这道题在不同语言环境里都跑过一遍说说实测数据供你参考。Python 版本对一万个元素的数组耗时在毫秒级几乎感觉不到。C 版本更快毕竟没有解释器开销。如果你的数组是十万、百万级双指针解法依然能轻松扛住因为它的复杂度是线性的且没有任何额外内存分配。极端情况我也测了全部元素都一样比如一百万个 1。这种情况 fast 会一路扫到底slow 始终停在 1最后返回 1期间只做了一次赋值。表现非常稳定。另一种极端是全部元素都不一样fast 和 slow 始终同步移动每次都会执行一次自身赋值整体耗时最大但依然是 O(n)。所以这道题不存在性能隐患你唯一需要担心的就是逻辑写没写对。从我自己看别人代码的经验来说这题写错的概率比很多人想象得高得多尤其是slow - 1和slow - k这种下标偏移的表达方式特别容易在压力下写拧巴了。最后再分享一个小技巧自测的时候不要只测题目给的用例把空数组、单元素数组、全重复数组、无重复数组这四类边界全部跑一遍。这四个用例覆盖了这道题 90% 以上的逻辑分支全部通过基本就能直接提交了。