刷 LeetCode 的朋友应该都有这种感觉简单题常常不是真的简单更像是一层窗户纸。删除有序数组中的重复项题库里第 26 题就是典型的窗户纸题目——所有解法摆出来也就十来行代码但如果你没想明白为什么用双指针为什么覆盖不会丢数据看答案以为自己懂了合上答案自己写又卡住。这篇文章我想把这道题从题意、思路演进、代码细节到边界情况完整拆一遍给你一份能直接拿去复盘和讲给别人听的完整笔记。这道题适合三类人看刚开始刷题、想打好数组基础的新手准备面试、需要把双指针思想讲清楚的求职者还有刷过一遍但想整理通用套路的进阶玩家。核心价值就一句话搞懂它你就同时掌握了原地修改和快慢指针这两个高频考点的标准打开方式。1. 题目到底在考什么有序数组的原地去重1.1 先说清楚输入输出长什么样题目给你的条件很明确一个按非递减顺序排列的整数数组nums也就是说数组整体是升序的允许重复值存在比如[0,0,1,1,1,2,2,3,3,4]。要求你做两件事原地删除重复出现的元素让每个元素只出现一次。返回删除后数组的新长度。原地这个词是重点。你不能另外开一个新数组再把结果装进去必须直接在原数组上操作。判题系统最终会检查你返回的长度k并且验证数组的前k个元素确实是无重复的、相对顺序保持不变。这里有个很多新手会忽略的细节LeetCode 的判题机制只关心数组前k个位置的内容k之后的位置随便是什么值都无所谓。这意味着你写代码时不需要、也不应该去把后面的元素清空你只需要保证前k个位置正确即可。1.2 为什么有序是这道题最大的突破口如果数组是乱序的去重通常得借助哈希表来记录哪些值见过如果数组有序重复的元素必然紧挨在一起。这个性质直接决定了最优解可以做到只遍历一遍数组、且不用额外空间。打个比方有序数组去重就像整理一叠已经按编号排好的文件重复的编号都在相邻位置而无序数组去重就像从一堆乱放的卡片里挑出不同编号你不用小本子记一下是没办法确认某个编号到底见没见过。题目特意强调有序就是在暗示你别用哈希表用指针就够了。1.3 所谓 O(1) 额外空间究竟是什么约束题目要求使用 O(1) 额外空间完成也就是说除了函数调用栈和几个整型变量你不能再申请跟数组规模相关的存储。这个约束直接排除了复制到新数组和哈希表两条路逼迫你在数组内部想办法挪数据。我第一次做这道题时其实走过弯路想着先统计每个元素的出现次数再按次数把数组重构一遍。这个思路本身没问题但统计需要哈希表空间复杂度就变成 O(n)不符合题目要求。后来我才意识到题目要的不是聪明的统计方法而是如何用最朴素的方式在数组内部腾挪。这个认知转变很重要它会直接影响你后面做一系列数组题目的思维方式。2. 暴力解法为什么能过但必须淘汰2.1 最直觉的做法一边遍历一边删除很多人拿到题的第一反应是遍历数组如果发现nums[i] nums[i-1]就把nums[i]删掉。这个想法很自然但在数组上做删除操作意味着要移动后面所有元素时间复杂度是 O(n²)。而且如果用 C 的vector::erase或 Python 的list.pop删除过程中迭代器/索引会失效还要小心翼翼地回退索引代码写起来很别扭。如果你用的是 Python确实可以写出看起来很简洁的版本def removeDuplicates(nums): i 1 while i len(nums): if nums[i] nums[i-1]: nums.pop(i) else: i 1 return len(nums)这段代码逻辑没问题也能通过 LeetCode 的测试。但它有两个隐患第一pop操作在列表中间执行是 O(n) 的最坏情况下整体复杂度 O(n²)第二它没有体现原地覆盖的思想只是利用了编程语言提供的便利。在面试中如果只写出这个版本面试官多半会追问一句你能不能只遍历一遍就完成2.2 暴力法的瓶颈本质是位置移动的成本数组这种数据结构的特点是随机访问 O(1)但中间插入或删除需要搬动后续所有元素。所以凡是涉及数组删除的题目只要数据规模大一点O(n²) 就无法接受。LeetCode 的测试用例里数组长度可以到 3 万甚至更大O(n²) 虽然不至于超时但也已经处在危险边缘。真正应该学会的思维方式是转换目标不追求物理删除重复元素而是追求把不重复的元素依次放到数组前部。后者的代价是 O(n)因为每个元素最多被移动一次。这就是双指针方案的核心思想。2.3 从删除思维切换到覆盖思维覆盖思维听起来可能有点反直觉——直接往原数组上写值不会弄丢后面还没处理的数据吗答案是不会因为快指针永远走在慢指针前面慢指针写的位置一定是快指针已经扫描过的位置。快指针才是探索者慢指针是记账员记账员永远不会写到探索者还没去过的地方。这个思维切换成功后你会发现很多数组题都变简单了删除元素、移动零、去除重复项本质上都是同一套覆盖前移逻辑。所以这道题的价值不只是解一道题而是帮你建立一种解决数组类问题的通用策略。3. 双指针解法从推导到代码的完整链路3.1 快慢指针的语义设计双指针解法里两个指针的角色必须非常清晰慢指针slow指向下一个不重复元素应该存放的位置。初始时slow 0因为第一个元素无论如何都要保留它是基准。快指针fast负责遍历整个数组寻找和当前保留元素不同的新值。初始时fast 1直接从第二个元素开始探索。两个指针的初始值设定是有讲究的。slow从 0 开始是因为下标 0 的元素一定是不重复的不需要比较就知道它要被保留。fast从 1 开始是因为我们要从第二个元素起逐个判断这个元素是否和上一个保留的元素重复。3.2 核心判断逻辑什么时候覆盖什么时候跳过遍历过程中永远拿nums[fast]和nums[slow]比较而不是和nums[fast-1]比较。这点很多人写错两种比较方式在大多数情况下结果一样但在某些场景下会有微妙差异后面我会单独说明。先记住和nums[slow]比较语义是当前快指针发现的值是不是一个新的、和已保留集合末尾不同的值。判断逻辑只有两种情况nums[fast] nums[slow]说明遇到了重复值不需要保留fast继续往前走。nums[fast] ! nums[slow]说明找到了新的不重复值。此时先把slow加 1给新值腾出位置再把nums[fast]的值写到nums[slow]上最后fast继续往前。整个过程结束后slow的值加 1 就是新数组长度因为它指向的是最后一个被保留元素的位置位置编号加 1 就是元素个数。3.3 手动走一遍完整流程拿[0,0,1,1,1,2,2,3,3,4]举例初始slow 0, fast 1nums [0,0,1,1,1,2,2,3,3,4]fast1nums[1]0等于nums[0]0跳过fast2fast2nums[2]1不等于nums[0]0slow变为 1nums[1]nums[2]1数组变为[0,1,1,1,1,2,2,3,3,4]fast3fast3nums[3]1等于nums[1]1跳过fast4fast4nums[4]1等于nums[1]1跳过fast5fast5nums[5]2不等于nums[1]1slow变为 2nums[2]nums[5]2数组变为[0,1,2,1,1,2,2,3,3,4]fast6后续同理fast发现 3 时填入nums[3]发现第二个 3 时跳过发现 4 时填入nums[4]最终slow 4返回slow 1 5。数组前 5 位是[0,1,2,3,4]正确。注意一个细节在覆盖过程中数组后面残留的旧值比如步骤 6 中nums[3]仍然是 3完全不用管因为判题只看前k个位置。3.4 完整代码与复杂度分析下面是几种主流语言的实现逻辑完全一致def removeDuplicates(nums): 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 1var removeDuplicates function(nums) { if (nums.length 0) return 0; let slow 0; for (let fast 1; fast nums.length; fast) { if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; };int removeDuplicates(vectorint nums) { if (nums.empty()) return 0; int slow 0; for (int fast 1; fast nums.size(); fast) { if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; }复杂度分析时间复杂度O(n)快指针遍历数组一遍每个元素访问一次。空间复杂度O(1)只用了两个整型变量没有额外数据结构。这个方案已经是最优解因为至少需要遍历一遍数组才能知道有哪些元素不可能做到比 O(n) 更快。4. 三个隐藏细节和 nums[slow] 比较 vs 和 nums[fast-1] 比较的差别4.1 两种比较方式真的等价吗网上很多题解写的是if (nums[fast] ! nums[fast - 1])然后nums[slow] nums[fast]。乍看之下用nums[fast-1]和用nums[slow]作为比较基准在有序数组去重这个场景下结果几乎总是相同的。这是因为当fast递增时如果中间跳过了重复值nums[fast-1]很可能仍然是那个重复值而nums[slow]是指向最后一个已保留的唯一值它和nums[fast-1]在很多情况下值相同。但有一个微妙区别值得注意直接用nums[fast-1]比较隐含了上一个元素就是已保留集合的末尾这一假设。在去重场景下这个假设通常成立因为重复值都挤在一起只要数组有序fast-1位置上的值要么和slow指向的值相同要么就是刚刚被跳过的重复段里的值。可如果题目变形为删除无序数组中的重复项用nums[fast-1]就完全错了因为无序时上一个元素不代表已保留的末尾。所以从代码的可迁移性角度我建议你养成和nums[slow]比较的习惯这是一个更稳健、更能应对变式的写法。4.2 为什么覆盖操作不会弄丢未处理的数据这是数组双指针最核心的一个疑问。覆盖操作是nums[slow] nums[fast]slow永远小于或等于fast。当slow fast时nums[slow]是已经被快指针扫描过、不再需要保留的旧值当slow fast时说明从开头到现在完全没有重复此时nums[slow] nums[fast]等于原地赋值什么都没变。换句话说慢指针永远在快指针的身后或同位置它写的位置必然是已经被快指针看过且判定为不需要保留的位置。所以覆盖是安全的不会破坏尚未扫描的数据。这个性质值得自己推导一遍理解了它你对双指针的信心会完全不一样。4.3 边界条件测试清单面试或做题时边界条件是最容易扣分的地方。我建议你提交前用下面这些用例过一遍代码测试用例期望输出说明[]0空数组直接返回 0[1]1单元素数组直接返回 1[1,1,1]1全部重复只保留一个[1,2,3,4]4完全无重复数组不变[0,0,1,1,1,2,2,3,3,4]5混合场景经典用例[-3,-3,-2,-1,-1,0]4负数场景逻辑同样适用如果你写了if not nums: return 0这个保护空数组就不会出问题如果没有这个保护直接在nums[0]上操作就会越界崩溃。单元素数组也要注意循环体内range(1, 1)不会执行直接返回slow 1 1逻辑天然正确。4.4 从删除重复项到删除指定值的迁移双指针方法不仅限于去重。LeetCode 第 27 题移除元素、第 283 题移动零本质上都是同一个套路只是比较逻辑和写入逻辑稍作变化。移除元素给定一个值val要求原地移除所有等于val的元素。比较基准变成是否等于 val快指针扫描遇到不等于 val 的值就写入慢指针位置。移动零要求把数组里所有 0 移到末尾同时保持非零元素相对顺序。快指针扫描遇到非零值就写入慢指针位置结束后慢指针后面的位置补 0。如果你真正理解了慢指针指向下一个应该写入的位置快指针寻找有效值这个抽象模型这三道题就是一通百通的关系。我建议你按删除重复项 → 移除元素 → 移动零这个顺序连续刷体会同一套框架在不同题目里的变体。5. 一道题背后双指针技巧的通用框架5.1 双指针的两大类快慢指针与左右指针双指针技巧在算法题里是个大家族主要分两类快慢指针两个指针同向移动通常一个快一个慢。适用于链表判环、数组去重、链表找中点、移动零等场景。左右指针两个指针从两端向中间移动。适用于有序数组两数之和、反转数组、回文判断、盛水最多的容器等场景。本题属于前者而且是最经典的入门载体。因为它的逻辑足够简单没有复杂的数学推导却完整展示了快慢指针的协作模式一个负责探索一个负责记录。把这个例子吃透后面遇到链表的快慢指针题目时你会有一种似曾相识的感觉学习成本会降低很多。5.2 双指针为什么能把 O(n²) 降成 O(n)暴力解法的问题在于每次删除一个元素都要把后面所有元素往前搬搬移次数和数组长度相关。双指针的核心优化是通过一次遍历把每个元素最多移动一次。更精确地说暴力解法在删除时重复搬移了同一个元素多次删一次搬一次而双指针方案里每个元素要么被快指针扫描一次要么被慢指针写入一次整体操作次数是线性的。这背后是一个更通用的思想——用覆盖代替删除。在很多数组题目中删除是昂贵的而覆盖是廉价的你应该尽量把昂贵操作转化为廉价操作。5.3 写题时的思考顺序先抽象再编码看到一道数组题我的建议是先别急着写代码按这个顺序想题目要求什么是物理删除还是覆盖即可输入有什么特殊性质有序、无序、范围固定能否用两个指针分别承担不同职责指针的初始位置和移动条件分别是什么边界条件空数组、单元素、全重复怎么处理以本题为例题目要求原地删除输入有序自然想到快慢指针慢指针负责记录新数组的写入位置快指针负责扫描初始化慢指针 0、快指针 1比较逻辑是不等则写入边界是空数组返回 0。整个过程一旦理清代码几乎是水到渠成的事。5.4 一题多解除了双指针还有别的思路吗严格来说针对有序数组去重这个具体场景双指针已经是最优解。但如果你放宽限制还可以考虑利用语言特性Python 可以用dict.fromkeys(nums)去重但需要额外空间且不满足原地要求。二分查找边界对每个唯一值找它在数组中的最后出现位置然后移动元素。这个思路可以解决删除有序数组中的重复项 II那种允许重复两次的变体但实现复杂。额外数组拷贝最简单但完全违背题目精神。了解这些思路的意义在于面试中面试官可能会在双指针基础上进一步变形比如如果每个元素最多保留两个副本呢LeetCode 第 80 题。那时你就需要在双指针框架上增加一个计数器记录当前保留了几个副本。理解了基础版的指针语义变形题才不会被吓住。6. 实测经验提交、调试、复盘的最佳路径6.1 我建议的第一次动手顺序第一次做这道题时不要直接抄代码。按下面的步骤来自己在纸上画一个数组把slow和fast两个指针标出来手动模拟一遍完整流程。用你熟悉的语言写第一版不要追求优雅先保证逻辑正确。提交到 LeetCode看测试报告重点看哪些用例没过。如果某个用例没过打印出每一步的数组状态和指针位置逐个对比期望行为。通过之后再思考代码能否精简是否有更直观的写法。这套流程适用于几乎所有算法题。很多人在第 3 步就停了然后去看题解——这其实是提升最慢的方式。亲手撞一次边界条件比看十篇题解都有用。6.2 我在调试中实际遇到过的坑我第一次写这题时用的是nums[fast] ! nums[fast-1]作为判断条件提交后所有用例都过了但后来做变形题删除有序数组中的重复项 II时这个写法立刻给我带来麻烦。因为那道题需要知道已经保留了几个相同元素nums[fast-1]不能提供这个信息我必须改成从nums[slow]和一个计数器共同判断。从那以后我统一改成和nums[slow]比较避免了思维混乱。另一个容易踩的坑是返回值弄错。有人最后会直接返回slow但slow是下标不是长度从 0 开始数所以要加 1。这个错误在数组长度为 0 或 1 时都看不出来但在混合用例下会差 1。建议最后写一行注释提醒自己slow 是下标长度是 slow1。6.3 如何用这道题举一反三建议你连刷以下四道题按顺序练习26. 删除有序数组中的重复项本题27. 移除元素比较基准从是否重复变为是否等于指定值283. 移动零额外增加末尾补零的步骤80. 删除有序数组中的重复项 II允许保留两个副本需要引入计数器刷这四道题时你最好维护一份自己的双指针模板笔记记录通用的代码框架和每次变形时改动了哪一行。等这四道题全部吃透你再看其他用到双指针的题就不会有畏难情绪了。我个人实际体会是把一道经典题彻底消化成自己的思维习惯效果远好于囫囵吞枣刷十道题。每次刷题前先默写一遍快慢指针的语义没过多久你就会发现这类题已经变成肌肉记忆了。
