这套题我刷过很多遍也用它在实际业务里处理过数据清洗的逻辑。今天聊聊“删除有序数组中的重复项”这道题不光是给出解法而是把整个思考链路、踩过的坑、以及从这道题延伸出来的一类双指针套路一次性讲透。先说结论这道题表面上是“去重”本质上考的是“原地修改数组”的能力——也就是在不新建额外数组的前提下通过指针游走把数组的前缀整理成不重复的有效区。这在真实的开发场景里很常见内存受限的嵌入式环境、大数据量下的原地归约、或者面试时考察候选人能不能在有限空间里把问题理清楚。所以它不只是一道“面试背题”更是一道训练指针思维的基础课。无论你是刚接触数据结构的新人还是复习算法准备换工作这篇文章都会有用。我会从题目隐含的条件开始拆推演完整的解题过程给出多语言的落地实现再把变体题比如“保留至多K个重复项”一起解决掉。1. 题目理解的第一步有序数组这个前提到底给了我们什么很多人上来就写循环结果边界条件一团乱。我建议先停一下把“有序”两个字的价值想清楚。它意味着相同元素在数组里是连续排布的不可能出现“1, 2, 1”这种跨越式的重复。这个特性直接决定了我们不需要额外的哈希表去记录“哪些值见过”只需要比较相邻元素即可。换个角度看问题如果数组是无序的那么去重就变成了一道新题必须借助哈希集合或者先排序。排序本身是O(nlogn)哈希集合需要O(n)的额外空间。但“有序”这一条让时间复杂度和空间复杂度都能做到极致——时间复杂度O(n)额外空间O(1)。这也是为什么面试官特别爱出这道题它在最简单的数据结构上考察你对最优解的理解是否到位。再说“原地”这个要求。很多人不理解为什么不能新建一个数组把不重复的元素装进去再返回。本质上函数返回的是数组的新长度而调用方仍然通过原数组的内存地址来访问数据。如果新建数组调用方根本看不到新数组的内容。所以必须原地修改把不重复元素“压实”到数组的前面后半部分即使留下旧值也无所谓因为逻辑上的有效范围已经被新长度切断了。这个“压实”的思想是整个双指针解法的灵魂。用生活化的类比来解释想象一排座位观众里有重复的人同一个体出现多次现在要让每个人只占一个座位且保持原来的先后顺序。你不能把人拉出去重新排只能在现有的座位里把重复的人往后挪然后把“有效观众数量”告知检票员。双指针就是两个工作人员——快指针负责逐个检查观众慢指针负责维护“已经安置好的座位边界”。2. 双指针解法推演从暴力拷贝到原地覆盖的完整思考链2.1 第一反应为什么不能直接删除元素如果是在数组里直接执行删除操作每次删除一个元素后面的元素全部要往前搬移这个操作的平均代价是O(n)。如果重复元素很多总的时间复杂度会退化到O(n²)。这在实际开发里是不可接受的尤其是数据量上了百万级别之后性能会惨不忍睹。所以“删除元素”这个思路虽然在语义上直接但在数组这个连续存储结构上代价太大。链表删除是O(1)数组删除是O(n)因为它们的数据组织方式不同。这道题选择数组作为载体其实就是暗示你不要想着物理删除要想办法逻辑覆盖。2.2 第二个想法哈希表记录出现过的值用哈希集合保存每个出现过的元素遇到新值就放入结果区遇到旧值就跳过。这个思路是正确的但有两个问题。第一需要O(n)的额外空间不符合“原地”的约束。第二对有序数组来说哈希表其实大材小用了因为相邻比较就够了根本不需要记住所有历史值。这种“用最普适的方法解决特化问题”的做法不是说错而是没抓住题目的隐藏线索。“有序”这个条件已经摆在那里了不利用起来就好比明知道钥匙在口袋里面还在满屋子翻找。2.3 正解双指针的诞生边界先把两个指针的职责定义清楚。慢指针slow指向“下一个不重复元素应该放置的位置”快指针fast负责“扫描整个数组寻找新的不重复元素”。两者初始都指向位置1因为位置0的元素一定保留不需要比较自己和自己的值。fast每次向后移动一位当nums[fast]和nums[slow-1]也就是当前已确认有效区的最后一个元素不相等时说明发现了一个新元素。此时把nums[fast]赋值给nums[slow]然后slow加一。fast继续走。如果相等说明是重复项fast直接跳过。这里有一个关键细节为什么用nums[slow-1]而不是nums[slow]因为nums[slow]这个位置可能是空的、等待被覆盖的位置里面可能还残留着旧值用它做比较会出错。而nums[slow-1]是已经确认过的、有效区的最后一个真实元素用它做参照才可靠。我见过好几个同学在这里写错慢指针一开始就快慢分不清结果比较基准一错后面全乱。用一句口诀记忆这个算法慢指针画边界快指针找新值比的是新值与边界末尾写的是新值覆盖边界位置。3. 代码落地多语言实现与每一行背后的含义3.1 C 实现最贴近底层思维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; }解释几个细节空数组提前返回是因为后面要访问nums[slow-1]空数组会越界。这个习惯在工程代码里很重要——先处理边界再进入主逻辑。slow从1开始是默认nums[0]为第一个不重复元素。不要从0开始否则第一次比较nums[fast]和nums[-1]会访问非法内存。fast从1开始是因为0号元素已经作为基准了遍历从1号开始比较才有意义。从0开始会让第一个元素自己和自己比较浪费一次循环且可能出错。3.2 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 slowPython的写法之所以简洁是因为它不需要显式管理指针的加法for循环本身就在帮fast自增。但要注意的是Python的列表是对象引用赋值操作nums[slow] nums[fast]是引用替换不是值拷贝。这道题处理的是整数没有影响但如果数组存的是大对象这种原地覆盖实际上只是移动了引用不会有深拷贝开销性能反而好。3.3 JavaScript 实现面试高频语言var removeDuplicates function(nums) { if (nums.length 0) return 0; let slow 1; for (let fast 1; fast nums.length; fast) { if (nums[fast] ! nums[slow - 1]) { nums[slow] nums[fast]; slow; } } return slow; };JavaScript的数组本身自带splice方法可以直接删除元素但用splice的时间复杂度是O(n)而且频繁修改数组长度会影响引擎优化。这里用双指针覆盖一次遍历解决问题是最好的方案。3.4 三份代码的共性校验三个语言的实现逻辑完全一致这也说明双指针是一个语言无关的算法思想。我习惯在写完代码后自己脑子里跑一遍用例用一个重复较多的数组来验证nums [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]慢指针slow1快指针fast从1开始。fast1nums[1]0等于nums[0]0跳过。fast2nums[2]1不等于nums[0]0覆盖nums[1]1slow变2。fast3nums[3]1等于nums[1]1跳过。fast4nums[4]1等于nums[1]1跳过。fast5nums[5]2不等于nums[1]1覆盖nums[2]2slow变3。后面同理最终slow5数组前五个位置变成[0, 1, 2, 3, 4]返回5。这个手推过程能帮你快速发现边界错误我建议每个初学者都至少完整走一遍。4. 测试与边界空数组、单元素、全部重复、全部不同的验证思路这个步骤很多人忽略但它恰恰是工程中真正的分水岭。面试时考官不会只看你的代码对不对更会观察你有没有测试意识。我整理了一张边界情况自查表你写完后可以对照检查输入数组期望输出有效区内容容易出错的点[]0空忘记判空直接访问nums[0][1]1[1]循环没进返回值是否正确[1, 1, 1]1[1]全部相同slow是否始终为1[1, 2, 3, 4]4[1, 2, 3, 4]没有重复时slow是否等于数组长度[1, 1, 2, 2, 3]3[1, 2, 3]中间阶段的覆盖是否正确逐个说明空数组是最简单的边界但它考验的是你是不是一上来就进入主逻辑。如果忘记判空后面的nums[slow-1]访问就会抛异常。一个成熟的工程师拿到任何输入第一反应永远是“边界条件是否安全”这是一种职业本能。单元素数组几乎没有存在感但它确认了“slow从1开始”这个初始化是否正确。循环条件fast len不满足直接返回slow1就是正确结果。如果你初始化slow0这里就会遇到问题——返回0等于告诉调用方“数组里没有元素”显然不对。全部重复的数组比如[7, 7, 7, 7]考验的是算法是否会在每次比较时都产生覆盖。我们走一遍slow1fast从1开始每次nums[fast]都等于nums[0]7fast一直走slow始终是1。最终返回1正确。但如果你的比较基准写错了——比如用nums[slow]而不是nums[slow-1]——情况就会完全失控。因为nums[1]已经被循环跳过从未被覆盖里面的值还是7碰巧能过但换一个输入就原形毕露。全部不同的数组比如[1, 2, 3, 4]考验的是覆盖操作是否“等价于自身复制”。每次比较都不相等所以nums[slow] nums[fast]其实写的是同一个位置因为slow和fast同步前进这种“自己赋值给自己”的操作在C里没性能问题编译器会自动优化掉。这组用例覆盖了“空、单、全同、全异、混合”五种典型输入你可以在任何语言的在线环境里跑一遍全部通过代码才算真正落地。5. 一个模板吃透一类题从“去重”到“保留至多K个重复项”比这道题本身更重要的是它的家族。只要把条件改成“每个元素最多出现K次”就衍生出一类变体题经典版本是“允许最多出现两次重复”。5.1 推广后的统一解法int removeDuplicatesK(vectorint nums, int k) { if (nums.size() k) return nums.size(); int slow k; for (int fast k; fast nums.size(); fast) { if (nums[fast] ! nums[slow - k]) { nums[slow] nums[fast]; slow; } } return slow; }你仔细看这个代码和原版的区别slow和fast的初始值从1变成了k比较基准从slow-1变成了slow-k。逻辑完全没变但适用范围一下子从“最多一个重复”扩展到了“最多K个重复”。5.2 为什么比较基准是slow-k它的含义是当前已经确认的有效区里允许出现K个相同的元素。新来的元素如果和前K个位置的元素值相等说明它将是同一个值的第K1次出现必须跳过。如果不等说明出现了新值可以收入有效区。用K2举例数组[1, 1, 1, 2, 2, 3]slow2fast2nums[2]1等于nums[0]1跳过。fast3nums[3]2不等于nums[0]1覆盖nums[2]2slow变3。fast4nums[4]2不等于nums[1]1注意这里比较的是speed-k1位置覆盖nums[3]2slow变4。fast5nums[5]3不等于nums[2]2覆盖nums[4]3slow变5。 最终得到[1, 1, 2, 2, 3]正确。我第一次写这个扩展版时把比较基准写成了slow-1导致结果跑到一半就全乱。后来想明白了slow-1是“最后一个位置”只适合K1的特殊情况通用情况下要看的是“是否已经达到了K次上限”也就是位置slow-K处的值。5.3 变体甚至不需要“有序”这道经典变体“移除元素”要求删除数组中所有等于某个特定值的元素它同样可以用双指针而且不需要数组有序。核心模板一模一样fast扫描slow维护边界只不过比较对象从一个动态值变成了一个固定值。所以说双指针的真正价值在于让你“一次学会处处使用”。6. 这类题真正在考察什么复杂度意识与工程思维的结合点6.1 面试官到底想看什么很多候选人五分钟就能写出这段代码但面试仍然挂了。原因通常是写完之后只会报答案说不出设计动机也不会分析复杂度。面试官真正考察的是三件事。第一你有没有意识到“有序”是一个可以利用的特殊条件。如果你一上来就用哈希表说明你缺乏对题目条件的敏感度。第二你能不能把“删除”抽象成“覆盖”这考察的是对数据结构底层存储方式的理解而不是背API。第三你能不能清楚地分析时间复杂度和空间复杂度并解释为什么这是最优解。关于复杂度分析有一个容易说错的地方。很多人把“只遍历一次”和O(n)混淆却忘记慢指针虽然也在移动但它不会超过快指针所以整个流程中每个元素最多被访问常数次。严格来说快指针访问一次慢指针最多访问一次整体是O(n)。空间上只用了两个整型变量O(1)额外空间没有任何随n增长的存储。6.2 工程中哪里需要这种“原地覆盖”真实的业务代码里很少直接叫“删除数组重复项”但类似的场景每天都在发生。比如日志数据清洗时需要把一堆按时间排序的日志记录里重复的ID去掉只保留第一条同时又不能把整个数组复制一份因为内存里可能有几百万条记录。再比如一些缓存队列的实现需要在有限的环形缓冲区里整理有效数据双指针覆盖的思路同样适用。还有一次我在处理配置文件合并时需要把多个来源的配置项按优先级合并成一份本质上也用到了双指针的思想一个指针指向输出位置另一个指针扫描源数据判定条件成立才覆盖写入。算法题和工程问题的距离往往只差一层“翻译”。6.3 如何向面试官讲解你的方案如果是在面试场景我建议你用这样的逻辑顺序表述而不是上来就写代码先说明观察到“有序数组”这一前提因此重复元素必然相邻。说明“原地”约束意味着不能新建数组必须覆盖。推出双指针方案一个指针维护有效区边界一个指针负责探索。给出代码并手动跑一个用例。用一句话收尾复杂度结论。这套表述最大的好处是让面试官跟着你的思路走而不是盯着代码猜。实际面试时有一个流程比代码结果更重要你展示了从条件推导方案的思考过程这比背下一百道题有用得多。7. 踩坑实录我自己写这道题时犯过的蠢错误7.1 比较基准用错这是我犯过最多次的错误。早期我写的是if (nums[fast] ! nums[slow])跑简单的用例能过但遇到[1, 1, 2, 2, 3]就挂。原因很简单nums[slow]这时候还在有效区里但它不一定代表“最近一次确认的元素”。有效区的最后一个元素应该是nums[slow-1]才对。这个错误非常隐蔽因为它在某些数据分布下能碰巧得出正确结果。比如[0, 0, 1, 1, 2]这种当fast走到第一个1时slow恰好是1nums[1]还是0还没被覆盖比较0和1不相等恰好覆盖结果对了。但如果换一个输入比如[0, 1, 1, 2, 2]fast走到第二个1时slow已经是2nums[2]还是1比较1和1相等结果正确跳过又碰巧对。我只是运气好直到用[0, 0, 1, 2, 2, 2]测试时才暴露出结果错误。所以我要强调边界条件的验证一定不能只靠一两个例子至少要覆盖“部分重复”“全部重复”“无重复”三种分布形态。7.2 忘记处理空数组这在C里是直接崩溃在Python里也会抛IndexError。虽然代码很短但很多人因为觉得题目简单就省略了边界检查。工程上有个铁律任何函数入口都要考虑输入是否可能为空。数组、字符串、指针、容器对象都要先问一句“它可能是空吗”。7.3 把slow和fast的初始值搞混有人觉得既然第一个元素不需要处理那slow应该从0开始fast从1开始。这样做的直接后果是第一次比较时nums[fast]和nums[slow]其实都是“有效区的第一个元素”如果它们相等说明这个值在数组里重复了你应该保留但只保留一份但slow仍然停在0下一次覆盖会覆盖掉第一个元素。我画了一个小示意图帮自己记住初始slow → nums[0], fast → nums[1] 比较基准nums[slow] 与 nums[fast] 是否相等 如果相等说明 fast 指向的是重复项跳过。 如果不相等说明 fast 指向新值先 slow再将 nums[fast] 赋给 nums[slow]。注意这个版本和上一节的正解有微妙的差别用先自增再赋值的方式避免了自己覆盖自己的问题。两种写法本质等价但先自增再赋值的版本不容易出错。不同的人可能有不同的习惯我的建议是选一种你理解的版本固定下来不要混着用。7.4 把题目理解成“删除元素后数组长度动态变化”有人会用while循环动态判断nums.size()每删除一个元素就改变长度导致循环条件失控。又或者用splice操作在迭代过程中修改数组。这两种做法在工程上会引发更严重的隐藏bug——迭代器失效。数组长度变化会使得“当前位置之后的所有索引”全部偏移一旦处理不巧轻则跳过元素重则索引越界。理解“返回新长度而不是真正删除元素”这个设计意图是避免走进这些歧路的关键。这道题的返回值之所以是“新长度”正是为了让调用方通过新长度来截断数组根本就不需要物理删除。8. 从这道题延伸出去的思维模型什么时候该用双指针经过这些年的练习和复盘我总结了一个经验双指针适合解决一大类“线性结构上的条件筛选”问题特征有几个。第一数据结构是数组或链表元素之间存在顺序关系。第二问题要求“筛选”出符合条件的元素或者“归约”出某种统计信息。第三最好能通过一次遍历完成且不希望使用额外空间。第四题目有条件线索比如“有序”“原地”“连续”“最多”等关键词。常见的双指针模型大概有这么几种模型指针关系典型场景快慢指针一个快一个慢起点相同数组去重、环形链表检测左右对撞指针一个从左一个从右相向而行两数之和、回文判断、反转数组滑动窗口左右指针同向移动窗口动态调整连续子数组问题、字符串子串问题归并指针两个指针分别来自两个序列合并两个有序数组回到“删除有序数组中的重复项”它用的是典型的“快慢指针同向移动”模型。这个模型的核心判断方式就是通过一个慢指针维持“有效前缀”快指针不断探索新元素根据题目条件决定是否将其纳入前缀。如果你想系统掌握这一类题我建议把下面这组变体都刷一遍它们共享同一个思维框架移除指定元素和这道题几乎一样基准是固定值删除有序数组中的重复项II允许最多两次重复用k2模板秒解移动零把所有非零元素移到前面双指针里的慢指针负责维护非零前缀合并两个有序数组从后往前填充可以避免额外数组你会惊讶地发现看起来完全不同的四道题内核都是同一套双指针思想只是指针的起点方向、比较的基准、以及覆盖顺序略有不同。一通则百通这就是刷题从量变到质变的临界点。9. 最后分享一点实战心得用这道题举一个现实例子。我之前在某开发项目里需要写一段数据清洗逻辑把一批按时间排序的事件流去重只保留每个事件类型的首次出现。当时第一反应就是套这个双指针模板只不过比较的不是整数而是事件对象里的type字段。整个方法十几行就写完了线上跑了几万条数据也没出过问题。反而是后来同事用了一个所谓“更简单”的方案用哈希集合边遍历边删除结果数据量大时页面卡了近半分钟。同一件事方案选没选对效果天差地别。所以别小看这道基础题。它训练的双指针思维在工作中很多时候能直接转化为生产代码里的关键逻辑。建议你手写至少三遍第一遍照着抄第二遍合上默写第三边尝试独立推导出K2版本的解法。三遍走完这个模板基本就刻进肌肉记忆里了。到那时候你再遇到任何“有序数组去重/筛选”类问题就能一眼看穿本质了。