LeetCode 26双指针解法：有序数组去重核心是覆盖而非删除

新手刷题绕不开的一道题就是LeetCode 26删除有序数组中的重复项。这道题在“新手友好题解与思路解析”这个标签下经常出现但真正动手做的时候很多人反而栽在了一个看似简单的要求上原地修改。我第一次刷这道题也翻了车下意识想的是把重复元素“删掉”然后新建一个数组存结果结果越写越复杂。后来才意识到这道题考的其实不是删除而是数组元素的“覆盖”和“指针推进”。这篇就围绕这道题把思路、推导、代码、易错点和扩展一起讲透适合刚接触数组和双指针的读者也适合想把这个经典套路彻底吃透的进阶选手。1. 题目到底在考什么——从描述里挖出隐藏约束LeetCode 26的题目描述本身不长但每个字都埋着信息给你一个有序数组要求原地删除重复出现的元素使每个元素只出现一次然后返回删除后数组的新长度。注意这里说的是“原地”也就是不能用额外的数组空间必须在传入的那个数组上直接操作。1.1 “有序”这两个字的价值很多新手忽略了这个前提——数组是有序的。有序意味着什么意味着所有重复的元素一定是紧挨在一起的不会出现“1 2 1”这种重复元素中间隔着别的数的情况。正因为重复项连续排列我们判断“当前元素是否需要保留”只需要跟它前一个保留下来的元素比较就行不需要回头去遍历整段数组。对比一下如果数组是无序的同样的去重需求你大概率会想到用哈希表记录“哪些元素已经出现过”。但哈希表带来的额外空间是O(n)这在“原地修改O(1)额外空间”的约束下直接被否决。所以“有序”这个前提条件基本上就是出题人在提示你去重这件事可以做得比“查表”更轻量。1.2 原地修改的限制意味着什么“原地”两个字的约束力很强。它排除了两种看起来很自然的做法新建一个数组把去重后的元素依次放进去再拷回来——额外空间是O(n)不合格。用列表类的数据结构比如动态数组、链表来辅助去重——同样不符合原地要求。能做到原地修改的工具其实只有一个在数组本身做覆盖写入。你要把那些“应该保留”的元素按照顺序重新写到数组前面的位置最后把数组逻辑上的长度截断。题目不要求你物理上把元素从内存里抹掉只要求你返回一个新长度并且保证新的长度范围内不包含重复元素。理解到这一步整道题的解法基本就浮出来了。1.3 换个角度看“删除”“删除”这个词容易让人产生误解——好像要把元素真的移除后面的元素还得整体往前挪。数组删除一个元素确实是这个代价挪完后面的元素位置都变了而且要维持有序性这就是O(n)的搬移。如果对每个重复元素都做一次搬移最坏情况下整体复杂度会变得很糟糕。实际上题目根本不要求你“保持数组后面的部分有意义”。LeetCode的评测只检查新长度范围内的元素是否正确新长度之后留着什么内容完全不管。所以正确的姿势不是“删除”而是“前移”把不重复的元素依次往前写用覆盖的方式把旧值冲掉。这个视角一旦转变重复元素自然就不会出现在前面的有效区间内了。2. 双指针思路从哪来——从“覆盖写入”到“读写分离”既然确定了要用覆盖写入那么问题就变成怎么知道哪些元素该往前写、写到哪个位置上去这需要两个角色配合——一个指针负责在数组里往前探索看当前元素跟上一个保留的元素是不是重复另一个指针负责记录下一个不重复元素应该落位的位置。这就是双指针。2.1 快慢指针的经典角色分工在LeetCode 26里双指针通常叫快指针和慢指针或者读指针和写指针。我更习惯叫它们读指针和写指针因为这样语义特别清晰读指针快指针负责“读”数组每轮向后走一步检查每个元素。写指针慢指针负责“写”数组只有遇到不重复元素时才把读指针指向的值写到写指针指向的位置然后写指针向后挪一位。用生活化的例子来说就像你拿到一摞已经按时间排好序的照片想要挑出不重复的时刻然后把挑出来的照片按顺序摆到一个新相册里。只不过这里的新相册就是这本相册自己的前几页你把有价值的照片往前放后面的旧内容被盖掉也无所谓。2.2 为什么不是删除而是覆盖假设数组是 [1,1,2]如果采用“删除式”思路发现第二个1跟前面重复把它删掉后面的2要往前挪一位得到 [1,2]操作一次还行。但如果数组一长比如 [1,1,1,1,2,2,3,3,3]每删一个重复项就要搬移一批元素频繁搬移会让耗时明显上升。覆盖式思路完全不一样读指针从头到尾扫一遍发现第一个1直接写入位置0第二个1跟写入区的最后一个元素比较发现重复就直接跳过不产生任何搬移遇到2时跟写入区最后的1比较不同就写到位置1。整个过程数组的总长度没变元素的物理位置也没大动只是前面几个位置上被重新写成了“有意义的”元素。这种操作的代价每次都是O(1)整体就是一次线性扫描。2.3 为什么写指针的初始位置有讲究常见写法里有两种初始化写指针从0开始第一个元素总是要保留的所以可以先写入再移动。写指针从1开始默认第一个元素已经保留在原位从第二个位置开始准备接收后续的不重复元素。两种写法都能得到正确答案但第二种写起来更自然。因为它暗含了一个断言第一个元素永远需要保留。不管你数组里有多少重复项第一个元素肯定不是重复的重复的定义是“已出现过”而它是第一个没出现过。所以慢指针从1开始直接跳过对第一个元素的无意义判断代码会清爽很多。这也是一种常见的边界优化新手写代码时意识不到但其实很关键。3. 核心解法分步推导——从伪代码到逐行实现思路理清了代码就水到渠成。这一节我们一步步推导先处理边界情况再走一个具体例子最后给出完整代码。3.1 边界条件先处理掉做题先看边界这是习惯问题。对这道题来说最容易想到的就是空数组一个元素都没有长度就是0也不需要做任何去重直接返回0。另一个值得一提但仍能自然处理的场景是长度为1的数组它没有重复元素按流程走慢指针初始是1循环里读指针从1开始跟写入区最后一个元素比较相同的话跳过最终返回的长度就是1正好符合预期。边界处理得干净后面主循环就能少很多空指针和越界的隐患。3.2 走一遍例子从 [0,0,1,1,1,2,2,3,3,4] 看指针变化说概念容易走一遍就真实了。假设输入是 [0,0,1,1,1,2,2,3,3,4]有序数组重复项都连续。初始化慢指针 slow 1快指针 fast 1。fast 1读到的值是0跟 nums[slow - 1]也就是 nums[0] 0 比较发现相等说明是重复项。slow不动fast继续走。fast 2读到1跟 nums[0] 0 比较不相等。执行写入nums[slow] nums[fast]即 nums[1] 1。slow变为2。此时数组状态暂时是 [0,1,1,1,1,2,2,3,3,4]前两位已经是有效区。fast 3读到1跟 nums[slow - 1] nums[1] 1 比较相等跳过。fast 4读到1跟 nums[1] 1 比较相等跳过。fast 5读到2跟 nums[1] 1 比较不相等写入nums[2] 2slow变为3。fast 6读到2跟 nums[2] 2 比较相等跳过。fast 7读到3跟 nums[2] 2 比较不相等写入nums[3] 3slow变为4。fast 8读到3跟 nums[3] 3 比较相等跳过。fast 9读到4跟 nums[3] 3 比较不相等写入nums[4] 4slow变为5。循环结束返回slow也就是5。数组前面的5个位置是 [0,1,2,3,4]完美。这个推演过程值得自己在纸上画一遍。我每次带人刷题都会强调不要只盯着代码看脑子里要有数组的画面——哪些位置被重新写过哪些位置是旧值残留指针之间隔了多少距离。画过一遍之后双指针的核心动作就再也不会忘了。3.3 代码实现Java版本逐行注释给出Java版本因为LeetCode上Java用得多。其他语言无非是语法差异逻辑完全一致。public int removeDuplicates(int[] nums) { // 边界处理空数组直接返回0 if (nums.length 0) { return 0; } // 慢指针下一个不重复元素应该写入的位置 int slow 1; // 快指针从第二个位置开始依次跟“写入区最后一个元素”比较 for (int fast 1; fast nums.length; fast) { // 如果当前元素不等于写入区最后一个元素说明不重复 if (nums[fast] ! nums[slow - 1]) { nums[slow] nums[fast]; slow; } // 如果相等说明重复快指针继续前进慢指针不动 } return slow; }几个细节值得单独说明慢指针同时也是“新数组的有效长度”所以最后直接返回slow不需要slow1之类的修正。为什么比较的是 nums[slow - 1] 而不是别的因为slow指向的是“下一个要写入的位置”它前面的那个位置里存的是最近一个被保留的元素。数组有序只要当前元素跟最近保留的那个不同就说明它不是重复项。如果你去比较 nums[fast - 1]那就错了——那只是数组物理上的前一个元素可能是已经被覆盖的旧值也可能是待处理的重复项参考性不强。写入这个动作本身是安全的因为fast一定大于等于slow所以 nums[fast] 的位置一定不会先于 nums[slow] 被覆盖覆盖顺序不会破坏源数据。3.4 复杂度分析时间O(n)空间O(1)时间上快指针从头到尾只扫了一遍数组每次循环内做的事情是常数级的比较和可能的赋值所以时间复杂度是O(n)。n是数组长度。空间上全程没有使用任何额外的集合、数组、哈希表几个整数变量占用的空间是常数级的空间复杂度O(1)。这也是这道题的根本约束——如果面试官追问你能不能优化你可以直接说明线性时间和常数空间已经是这个约束下的最优解因为至少要遍历一遍每个元素才能判断重复。4. 为什么返回长度而不是返回数组——题目的隐藏约定这道题有一个很容易让新手产生疑惑的点明明函数签名是int removeDuplicates(int[] nums)返回的是一个整数那数组去哪儿了其实答案在题目描述里“函数应该返回新的长度并且原数组 nums 的前面部分需要被修改成新的内容。”也就是说题目的输入输出协议是你要原地改数组然后告诉系统“这个数组现在有效的部分有多长”。4.1 评测系统怎么检查你的答案LeetCode的检测逻辑大致是这样拿到你返回的长度k然后检查 nums 数组前k个元素是否为去重后的有序序列。至于下标k之后还有没有旧值残留系统根本不关心。这也解释了一个常见现象很多人在本地ide里运行这段代码打印整个数组发现后面还跟着旧数字误以为自己写错了。其实没有只要你返回的长度正确并且前k个元素正确就完全满足题目要求。记得我刚刷题时在本地调试看到输出数组是 [0,1,2,3,4,2,2,3,3,4]一度以为自己没删干净后来才明白这个约定。4.2 为什么这种设计反而更合理从工程角度看数组的长度在创建时就是固定的你没法真正“截断”一个数组。在大多数编程语言里数组的长度是内在属性不是可以随意修改的。所以这类题目只能用“逻辑长度”来模拟删除数组还是那个数组只是我们认为有效的部分变成了前k个元素。这其实非常贴近实际因为很多底层系统就是用这种“维护一个有效水位线”的方式来管理定长缓冲区的。数据不用真的清空新数据写进来覆盖掉就行。4.3 面试中怎么回答“为什么返回长度”面试官如果追问你可以说“数组本身是定长的无法物理删除元素。这道题实际考察的是在定长结构中通过覆盖写入维护逻辑有效长度返回长度就是在告诉调用方如何切分有效区和废弃区。”这个回答既体现了对题目约束的理解也展示了底层数据结构的知识比只说“因为LeetCode要求这么写”要加分得多。5. 易错点与常见问题排查——新手翻车实录再简单的题踩坑的姿势也能五花八门。这一节把新手常遇到的问题整理成速查表并且逐个分析背后的原因。症状出错原因解决方式空数组报错或返回奇怪结果没处理 n 0 的边界开头加判断空数组直接返回0返回的数组第一个元素丢失慢指针从0开始且先更新慢指针再写入保证写入发生在慢指针位置再让慢指针自增或让慢指针从1开始数组出现未被去重的情况比较对象选错比较了nums[fast - 1]改为比较nums[slow - 1]确保参考的是“已保留区的最后一个元素”使用了HashMap或HashSet没注意原地修改和O(1)空间约束改用双指针覆盖方案无限循环快指针没有正确递增或循环条件写错确认 for 循环中 fast 不被跳过循环范围是 fast nums.length数组后面残留旧值怀疑自己错误不理解题目只检查新长度之前的内容无需处理残留值只要前k个元素正确即可5.1 踩坑实录一慢指针起始位置写错有同学写代码时让 slow 0然后在循环里先 slow 再写入结果返回的数组变成从第二个元素开始丢了第一个。正确的做法是让慢指针指向的是“下一个要写入的位置”所以写入时先写nums[slow]再slow。如果你不确定可以在第一轮循环加一个断点观察 slow 和 fast 的初始值以及写入顺序。慢指针初始化为1既符合“第一个元素天然保留”的逻辑也能避开这类顺序错误。5.2 踩坑实录二比较对象选错导致去重失效这是最隐蔽的错误。有人会写成if (nums[fast] ! nums[fast - 1])在 [0,0,1,1,1,2] 这种例子上第一次比较是0跟0相同跳过接着1跟前面的0比较不同写入继续1跟前面的1比较相同跳过。看起来也能工作但问题是它只判断“跟物理相邻的前面那个元素是否相等”依赖的是有序数组下重复项相邻的性质。可一旦慢指针跟快指针之间差开了距离数组物理位置前面的元素可能是已经被写入的新值也可能是还没被处理的重复项对比结果就不一定可靠了。右侧例子中如果数组变成 [0,1,1,1,2]用nums[fast - 1]比较遇到第二个1时前面的元素也是1能跳过但遇到2时跟前面的1比较不同写入返回结果似乎也对。可一旦快指针的位置落后于“已写入区的最后一个元素”的语义就可能在更复杂的输入下出问题。稳妥的做法只有比较写入区最后一个元素也就是nums[slow - 1]。5.3 踩坑实录三本地调试误以为没通过我之前带过一个同学他跑完代码后打印整个数组看到后面还有重复值立刻觉得自己代码错了。其实这是正常现象。你要检验自己的输出应该只看返回长度范围内的元素。用Arrays.copyOf(nums, slow)打印前slow个元素来验证就不会被残留值误导。这算一个很小的调试技巧但对新人来说还挺关键。6. 从去重到“保留k个重复项”——一道题的通用化扩展LeetCode 26的套路掌握以后其实可以无缝迁移到一类更通用的题目有序数组里每个元素最多保留k个。这个扩展在LeetCode 80“删除有序数组中的重复项II”里就用到了每个元素最多出现两次不能出现三次及以上。6.1 通用化思路把“比较前一个”换成“比较前k个”LeetCode 26的本质是“每个元素最多保留1次”。为什么我们比较的是nums[slow - 1]因为写入区最后那1个位置就代表着最近保留的元素如果当前元素跟它相同就意味着这个元素已经出现了不能再保留第2次。那如果允许出现2次呢我们就不再关心“是否出现过”而要关心“是否已经出现满2次”。由于数组有序如果当前元素跟nums[slow - 2]相同说明在保留区里已经有连续的两个当前元素了那当前这个就是第3个必须跳过。反过来如果跟nums[slow - 2]不同说明在保留区里至多只出现过1次当前元素那就可以放心写入。同理如果允许出现k次就把比较对象换成nums[slow - k]。这是这类题的通用公式。我后来刷到LeetCode 80时几乎没有额外思考直接把26的代码改了一行nums[fast] ! nums[slow - k]k传2就通过了。6.2 通用代码模板public int removeDuplicates(int[] nums, int k) { if (nums.length k) { return nums.length; } int slow k; for (int fast k; fast nums.length; fast) { if (nums[fast] ! nums[slow - k]) { nums[slow] nums[fast]; slow; } } return slow; }这个模板的边界逻辑要仔细想一下慢指针从k开始因为前k个元素天然可以保留即使它们全相等也没有超过k个。快指针也从k开始从第k1个元素开始判断。比较对象是nums[slow - k]它表示写入区里“往前数k个位置”的那个元素。如果当前元素等于它说明相同元素已经凑够k个了不等才允许写入。用这个模板LeetCode 26就是k1的特例LeetCode 80就是k2的特例。6.3 举一反三数组操作里的“读写分离”思想双指针去重看起来只是个小技巧但它背后是“读写分离”的思想一个指针负责读一个指针负责写写永远追着读走但写的位置不一定跟读同步。这个思想在很多场景里都会复用比如数组原地删除指定元素LeetCode 27、移动零LeetCode 283、按奇偶排序数组LeetCode 905本质都是在用快慢指针做原地过滤。你甚至可以把这个套路背成一个条件反射——一旦遇到“原地处理数组元素”的题就先想想能不能用快慢指针的读写分离来解决。7. 实操心得如何把这道题变成你的面试底牌作为一个刷过不少题的过来人我建议别急着把这道题划掉就算完。LeetCode 26虽然简单却是一个很好的“表现型题目”——你可以用它展示代码规范、边界意识、复杂度分析能力和扩展思维这些都在一道题里涵盖了。7.1 面试时怎么讲才能加分如果面试官让你做这道题别直接闷头写代码。先说思路“因为数组有序重复元素一定相邻所以可以用快慢指针。快指针负责扫描慢指针维护有效区的末尾。当前元素跟慢指针前一个元素不同就覆盖写入并发推进否则快指针直接跳过。这样能保证原地、O(1)空间、O(n)时间。”写代码时注意先写空数组边界再写主循环。写完代码后主动补充复杂度分析并提一句“慢指针同时就是新数组长度所以最后返回慢指针”。最后如果面试官有兴趣还可以补充“这个解法可以推广到保留k个重复项把比较对象改成 slow - k 就行”。这种层次递进的输出方式远比默写代码印象深刻。7.2 练习时给自己的额外挑战我自己刷题时习惯在通过之后给代码做三个小改造换成C版本时注意引用传递和指针写法加深对“原地修改”的理解。把代码改成“slow从0开始、先判断再决定是否写入第一个元素”的版本对比两种写法的边界差异从而彻底掌握慢指针的含义。尝试用while循环重写整个逻辑做到无论用for还是while都能快速写出正确代码。这些额外练习花不了多少时间但对加深理解帮助很大。尤其是写指针语义这件事代码怎么写都行但只有真正理解“slow指向下一个写入位置”之后遇到变体题才不会慌。7.3 关于这道题的最后一个心得双指针是我刷题过程中感受到最实惠的套路之一。LeetCode 26看起来平淡无奇但它是理解“快慢指针为什么能优化原地数组操作”的最短路径。以前我总觉得数组去重非得用集合学会了覆盖式写入以后才发现数据结构自带的API有时候反而会限制思路。数组本身只是个连续内存谁告诉你非要“删除”才能去重站在内存的角度看覆盖比删除效率高得多。这道题教给我的就是这个——处理数据之前先想想数据在底层长什么样很多“聪明解法”其实是顺着底层结构自然长出来的。保持这个视角刷题才会越刷越轻松。