双指针法原地去重：深入解析删除有序数组重复项的经典算法

“删除有序数组的重复项”——这道题常年出现在各类算法题库的入门位置几乎所有面试过算法岗位的人都刷过。但有意思的是很多人在“背会答案”的状态下能写出来一旦面试官追问“为什么快指针要从1开始”或者补一句“如果允许每个元素最多保留两个呢”就开始卡壳了。这题表面上是个入门题实际上把“指针思维”“边界条件控制”和“空间复杂度意识”三件事浓缩在了一起这也是它在笔试面试里反复出现的原因。我最早接触这道题是在给一个跨平台数据同步系统做数据预处理的时候。当时的场景非常朴素上游从多个数据源汇总了一批带重复的记录需要在不去重的情况下把新数据写进结果集而系统内存刚好吃紧没有余量再开一套数组。也就是说去重不能靠“新建一个数组然后再搬过去”这种直觉方案必须在原数组上就地完成。那个需求最后就是靠双指针解决的。所以这题对我来说不只是一个刷题任务它真的在工程里派上过用场。下面把这道题的考点、实现思路、常见变体和实际调试经验一条条说清楚。1. 题目到底在考什么1.1 一眼看穿考点题目本身不复杂一个有序数组 nums请原地删除重复出现的元素让每个元素只出现一次返回删除后数组的新长度。注意几个关键词“有序”“原地”“返回长度”。“有序”是这道题的题眼。数组有序意味着所有重复元素必然相邻不会出现“相同的值分散在两处”的情况。这是唯一能让双指针解法成立的前提。一旦数组无序重复元素就不会乖乖挨在一起那就得走哈希表路线空间复杂度立刻变成 O(n)。“原地”两个字劝退了很多人的第一反应——新建一个数组装去重结果再复制回来。这个做法在逻辑上完全正确但不符合要求。原地操作的本质是除了若干个临时变量不得申请和原数组规模相关的额外空间。“返回长度”也有讲究。题目不要求你真的把数组后半段的脏数据清掉只要求返回去重后的有效长度 k并且保证原数组前 k 个位置是按顺序的不重复元素。这个设计给了原地操作很大的余地——多出来的尾元素你不用管没人检查。所以这道题官方考点其实就一句话用一个能在原数组上完成的 O(n) 时间、O(1) 空间算法把重复元素“覆盖”掉。1.2 为什么“原地”两个字这么关键很多初学者不理解为什么面试官这么执着于“原地”。这背后是工程思维在起作用。在真实系统里数据量是动不动就上百万甚至上亿的。一个千万级的整型数组在 Java 里大约占 40MB 内存。如果每次去重你都 new 一个新数组内存直接翻倍。更麻烦的是在大流量接口里去重操作往往只是整个链路的一小步内存被这种小操作白白吃掉会直接影响下游的缓存命中率甚至触发内存告警。我当年做数据同步时遇到过类似情况。结果集数组本身是复用的每次同步后只是在尾部追加新数据追加前需要把上一轮的重复数据清掉。如果去重这一步用临时数组等于每轮同步都要分配一次大内存压测时 JVM 直接频繁 Full GC。改成双指针原地去重后GC 压力肉眼可见地降了下来。“原地”在这里不是单纯的题目限制它是一种写代码的习惯——在动手前先问自己一句这步操作真的需要额外空间吗这句话在性能敏感的场景里往往意味着几十毫秒和几十 MB 内存的差距。2. 双指针解法拆解2.1 为什么要用双指针有序数组去重的核心矛盾在于遍历数组需要一个指针标记“下一个不重复元素该放哪”又需要另一个指针。用两个指针各司其职是这个问题最自然也最省空间的解法。快指针负责“探索”从头到尾走一遍数组每到一个新位置就看这里的元素是不是一个“新值”。慢指针负责“记录”它指向的位置是下一个不重复元素应该写入的位置。你可以把慢指针想象成一支笔快指针想象成一只眼睛。眼睛看到新东西笔才落一下眼睛看到重复的笔就按兵不动。因为是有序数组“是否是新东西”的判断非常便宜——只要看当前快指针的值跟慢指针指向的值是否相等即可。为什么不用一个指针搞定因为单指针没办法同时兼顾“判断当前位置是否重复”和“覆盖旧位置”两件事。一个指针要么往前走要么停下来写无法在同一轮循环里既探查后续元素又维护前面的结果序列。所以双指针不是一种炫技的选择而是这个问题的最小可行方案。2.2 快慢指针的工程语义两个指针的初始位置在不同教材里写法略有差异但核心语义是一致的慢指针从 0 开始代表“已经处理好的不重复序列的最后一个位置”快指针从 1 开始代表“当前正在探查的元素”每轮循环都比较 nums[fast] 和 nums[slow]相等说明 fast 指向的是重复元素slow 不动fast 继续往前不相等说明 fast 发现了一个新元素先把 slow 往前挪一位再把 nums[fast] 的值覆盖到 nums[slow] 上这个“先移动再赋值”的顺序很重要。如果先赋值再移动会导致新值被写到旧位置上覆盖掉还没处理完的数据。循环结束后slow 指向的是最后一个不重复元素的下标所以新长度是 slow 1。工程上还有一个容易忽略的细节这个算法跑完后数组从 slow 1 到末尾的旧数据并没有被清空只是没人再看了。在实际工程项目里如果你接手的是别人写的算法代码千万别以为“返回长度 k 之后数组后半段就是空的了”。必要的话后续逻辑要根据返回的 k 来限制遍历范围而不是直接遍历整个数组。3. 代码实现与演进3.1 最简实现版本先看最通用、最容易背错但也是最推荐的写法。public int removeDuplicates(int[] nums) { if (nums null || nums.length 0) { return 0; } int slow 0; for (int fast 1; fast nums.length; fast) { if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; }这段代码有几个关键点值得多说几句。第一空数组和 null 的判断必须放在最前面。有些语言里数组取 length 本身不会报错但如果你后续要访问 nums[0]空数组就会越界。刷题时这层防护可以不加但工程代码里养成习惯没坏处。第二慢指针从 0 开始快指针从 1 开始这天然覆盖了“数组只有一个元素”的情况——循环不会进入直接返回 0 1 1不用额外写一个单元素分支。第三比较的是 nums[fast] 和 nums[slow]不是 nums[fast] 和 nums[fast - 1]。这两者在有序数组里大部分时候结果一样但含义不同。跟 fast - 1 比较判断的是“当前元素跟前一个元素是否相同”跟 slow 比较判断的是“当前元素是否是一个新的不重复值”。用 slow 作为基准更符合慢指针的语义在后续变体题里也更容易迁移。另一种同样常见的写法是把慢指针当成“下一个写入位置”而不是“已处理序列的末尾位置”public int removeDuplicates(int[] nums) { if (nums.length 0) { return 0; } int slow 1; for (int fast 1; fast nums.length; fast) { if (nums[fast] ! nums[fast - 1]) { nums[slow] nums[fast]; slow; } } return slow; }两种写法的时间复杂度都是 O(n)空间复杂度都是 O(1)区别只在于对 slow 这个变量语义的定义。我个人更推荐第一种因为“slow 指向结果序列的末尾”比“slow 指向下一个空位”更容易在调试时看清楚状态。但你不需要两种都背选定一种把它的每一步都理解透比贪多更踏实。3.2 边界条件的处理细节边界条件是这道题最主要的失分点也是最容易在面试时暴露“只是背了答案”的地方。第一个边界是空数组。返回 0 没争议但 null 呢在 Java 里这俩是两回事。刷题平台通常不会传 null但你自己写工具方法时一个 null 检查能帮你省掉一堆潜在的 NPE。第二个边界是单元素数组。上面两种写法都能自然处理不需要单独 if。但有些人的第一版代码会写成“先判断 nums.length 1 就直接返回”然后主逻辑只处理长度大于 1 的情况。这么写也没错只是多了一个分支代码更啰嗦。第三个边界是“全都是重复元素”和“没有重复元素”这两个极端。全重复时fast 走完整个数组slow 一直停在 0返回值是 1正确。没有重复时fast 每走一步 slow 也跟着走一步整个数组被原样覆盖一遍返回值是 nums.length也正确。两种极端情况能跑通基本可以说明指针移动逻辑没有大的方向性错误。第四个边界是重复元素连续出现多次的情况例如 [1, 1, 1, 2, 2, 3]。快指针遇到第一个 1 时跟 slow 指向的 1 相等不处理遇到第二个 1还是相等不处理遇到 2 时slow 移到下标 1把 2 写进去。之后继续走3 再写进去。最终数组前三位是 [1, 2, 3]长度 3。这个例子非常适合用来手推一遍指针变化推完基本就理解了整个算法的骨骼。我在给团队新人讲这道题时总让他们先在纸上画一个六格数组把 slow 和 fast 的每一步位置标出来。看起来慢实际十分钟就能把“为什么覆盖不丢失数据”想清楚。后边再遇到同类双指针题基本都能自己画出来。3.3 工程代码里的防御性改进刷题代码追求短小精悍但工程代码往往要额外考虑一件事调用方怎么知道去重之后数组的有效范围是哪里靠返回值当然可以但工程上很多老代码是通过出参来传数据的返回值经常被忽略。所以我在实际项目里会把这类“就地修改”的工具方法设计成这样返回新长度同时保证传入数组的前 k 位有效。调用方很明确要么接收返回值要么提前把原数组截断。如果你在团队里封装公共工具类建议在注释里写清楚这两点避免下游同学把你的方法当成“会返回一个新数组”的方法来调用白拿一个长度然后继续用原数组的完整长度遍历结果把脏数据也处理进去了。4. 变体与扩展从一道题到一类题4.1 变体一每个元素最多保留两个这是最经典的变体题有序数组每个元素最多出现两次原地删除多余重复项返回新长度。思路升级的关键在于判断条件从“是否跟 slow 指向的值相等”变成“是否跟 slow 往前数第二个值相等”。为什么是往前数第二个值因为“最多保留两个”意味着只要当前元素跟结果序列里倒数第二个元素相同那它一定是第三个重复值必须跳过如果跟倒数第二个不同说明它最多是第二个重复值可以留下。这个思路在代码实现上非常简洁也是我见过的最漂亮的变体之一。注意这里比较的是 nums[fast] 和 nums[slow - 1]这正是上一节说的“慢指针语义”的用武之地。如果你在用“慢指针指向结果序列末尾”的写法这个变体几乎是零成本迁移。public int removeDuplicatesMoreThanTwo(int[] nums) { if (nums.length 2) { return nums.length; } int slow 1; for (int fast 2; fast nums.length; fast) { if (nums[fast] ! nums[slow - 1]) { slow; nums[slow] nums[fast]; } } return slow 1; }仔细体会一下这段代码fast 从 2 开始是因为下标 0 和 1 的两个元素无论是否重复都在“最多两个”的允许范围内不需要处理。slow 初始为 1代表已处理序列的最后一个元素下标。fast 指向的每个元素只要跟已处理序列倒数第二个元素不同就允许写入。把这个变体学会之后你再遇到“每个元素最多保留 k 个”的通用版就很好理解了。无非是把 slow - 1 换成 slow - (k - 1)fast 的起始位置从 k 开始slow 的初始值设为 k - 1。一通百通。4.2 变体二无序数组的重复项删除有序数组可以用双指针做到 O(1) 空间但如果是无序数组呢两条路线一是先排序再双指针。排序本身 O(n log n)空间取决于排序算法整体可行但破坏了原始顺序很多时候业务不允许。二是用哈希表记录“已经见过的值”遍历一遍把第一次见到的值顺序搬到前面。空间 O(n)时间 O(n)但保持了原始顺序。这个方案在工程上更常用因为“保持顺序”在很多真实场景里是硬需求。代码示意public int[] removeDuplicatesUnsorted(int[] nums) { SetInteger seen new HashSet(); int write 0; for (int read 0; read nums.length; read) { if (seen.add(nums[read])) { nums[write] nums[read]; } } return Arrays.copyOf(nums, write); }这里额外提一个坑seen.add返回布尔值表示“这个元素是不是第一次出现”。这个返回值很多人不知道于是写成“先判断 contains再 add”两步操作在单线程下没问题但既不优雅也容易在并发场景埋雷。直接用 add 的返回值既省代码又更安全。4.3 变体三字符串去重与文件记录去重这题的思路还可以延伸到字符串和文件处理上。比如按行读一个日志文件要求把所有重复行去掉而且不能把整个文件读进内存。双指针就不能直接用因为文件不是随机访问的数组。但思路是一致的有序数据相邻重复边读边去重。我以前处理过配置文件去重就是先按字典序排序再逐行读取跟上一行比较相同就跳过不同就写入新文件。整个过程内存占用只有两行字符串。表面上看跟数组去重没关系底层逻辑完全一样。学算法最值得的回报就是这种“迁移能力”——你能在一道题里看到一类问题的影子。5. 调试心得与常见问题速查5.1 最容易踩的坑第一个坑返回值忘记加一。慢指针从 0 开始循环结束后 slow 指向最后一个不重复元素的下标返回值应该是 slow 1不是 slow。这个错非常隐蔽因为数组 [1, 2, 3] 这种没有重复的用例里slow 最后指向 2你返回 2看着挺合理实际真跑会错。一到“带重复项的用例”立刻暴露。第二个坑比较对象搞错。比较 nums[fast] 和 nums[fast - 1] 也能通过大多数测试用例因为有序数组里相邻元素是否相同和当前元素是否跟结果序列末尾相同在“去重一次”这个场景下等价。但一旦你把这个写法迁移到“保留两个重复项”的变体里就会出错——因为你要比较的是“当前元素跟序列倒数第二个是否相同”跟快指针自己前面的元素完全没有关系。所以从一开始就养成用慢指针做基准的习惯。第三个坑覆盖顺序写反。有些同学写成了nums[fast] nums[slow]把快指针指向的值给覆盖了然后整个数组就乱了。这个错误一跑测试用例立刻就暴露但它暴露的其实是对“慢指针是笔、快指针是眼睛”这个模型没有建立起来。笔永远往眼睛看到的新值方向写方向反了就是灾难。第四个坑语言层面的“伪原地”。Python 里如果你写nums list(set(nums))其实是在创建一个新列表再赋给变量原数组的内存并没有被复用。在 LeetCode 上它可能能过因为判题只看变量最终值但在工程里这种写法依然要分配一份新内存原地去重的目的完全没达成。用 Python 做题的人很容易忽略这一点因为语言的赋值语义让“看起来是原地”变得非常容易。第五个坑fast 的循环范围。有些初学同学把循环写成for (int fast 1; fast nums.length - 1; fast)少遍历了最后一个元素。当最后一个元素恰好是新值时就会被漏掉。记住fast 一定要走到数组末尾不能早早收工。5.2 面试官常追问的三个问题追问一“如果数组里有负数会影响结果吗”不会。这里只用到等值比较不涉及大小排序的比较负数不影响。这也是为什么算法本身不依赖具体数值范围。追问二“你能证明它为什么不会覆盖掉还没处理的元素吗”这是我最喜欢的一个追问。关键在于slow 永远小于等于 fast。slow 指向的位置是已经处理过的位置fast 指向的位置是尚未处理的位置。因为 slow 一定不会跑到 fast 前面去所以把 nums[fast] 覆盖到 nums[slow] 上永远不会覆盖掉还没看过的元素。追问三“这题的输入若是一个链表你还能用双指针吗”链表去重其实也可以双指针但链表的“覆盖”变成了“改 next 指针跳过重复节点”时空复杂度依然理想。这个追问本质上是考你会不会把数组上的指针思想迁移到链式结构上。5.3 我的个人调试经验刷这道题的时候我建议不要直接在编辑器里跑测试而是先在纸上手工模拟一遍 [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] 的完整过程。把 slow 和 fast 每一步的值、数组每一轮的样子写下来你会在大概第七步的时候突然想通“覆盖”为什么安全。我自己带新人时还会让他们做一个小实验在每次循环里把数组完整打印出来观察数组从中间开始变成什么样。你会发现慢指针走过的区域是“干净的”快指针前面是“还没动的”中间夹着一片“已经被覆盖过但没人关心的旧值”。这片灰色地带就是双指针算法付出的唯一代价。另外如果你在本地写测试记得加一条包含大量重复元素的用例比如三万个 1 后面跟三个 2。这种用例能很好测试“fast 一路狂奔slow 一直不动”的性能形态也不会因为元素太少而藏住问题。这道题背后真正值钱的不是那个双指针的套路而是一种思维习惯当你要消除一批数据里的冗余时先想想能不能在原有空间上通过“覆盖”来完成而不是急着申请新内存。这个习惯一旦养成你会发现在很多看似不相关的工程问题里都能找到它的影子。