删除有序数组的重复项：双指针原地去重算法详解

前阵子帮人做模拟面试十场里至少有三场会遇到这道题给定一个升序排列的数组要求原地删除重复元素让每个元素只出现一次最后返回去重后数组的长度。很多人嘴上说简单白板上一写就露馅——要么忘了“原地”这个硬性要求要么循环里直接调删除接口导致复杂度爆炸。今天这篇不绕弯子专门讲“删除有序数组的重复项”这个经典题。我会从题目拆解开始把双指针解法一步步推出来再给几种主流语言的实现、边界条件、常见变体以及面试现场能加分的表达。无论你是正在备战面试还是平时要处理有序数据集看完都能直接上手。1. 这题到底在考什么1.1 题目拆解三个关键词决定解法走向先把题面拆开看给定一个非降序排列的整数数组 nums原地删除重复出现的元素使每个元素只出现一次返回删除后数组的新长度。真正决定解题方向的不是“删除”两个字而是三个容易被忽略的限定词。第一个是“有序”。数组按从小到大排好所以相同值的元素一定会抱团出现不会零散分布。这意味着查重不需要任何“记忆结构”只要跟隔壁比一比就行。第二个是“原地”。你不能新开一个数组把不重复的元素挑出来再拷贝回去。说的直白点额外空间复杂度必须锁死在 O(1)。很多同学在新手期都犯过这个错先声明一个 list遍历一遍把不同的值加进去最后再复制回原数组。结果确实对了但脸也丢了因为那相当于额外开了一个 O(n) 的存储。第三个是“只返回长度”。这给了非常大的操作余地——你不需要把数组后半部分真正清理干净只需要保证前 k 个位置是去重后的结果返回 k 就行。残留的旧数据没人管逻辑长度是 k调用方就只读前 k 个。这三个词放在一起基本就把答案逼到了“双指针覆盖写”上面。后面我们会看到少一个条件解法可能完全不同。1.2 为什么“有序”两个字值千金如果数组是无序的重复元素散落在各个角落你必须先回答两个问题哪些值见过用什么记录要么额外开一个哈希集合要么先花 O(n log n) 的时间排序。而有序数组把“查重”简化成了“邻居比较”只需要看当前位置和上一个保留位置是否相同。打个比方图书馆书架上的书如果按编号排好了清理重复书籍时你从一排书前面扫过去看到两本编号一样的书挨着抽掉其中一本就行。但如果书架是乱序的你得先把所有编号记在小本子上或者把整个书架重新整理一遍成本完全不同。这也是这道题真正的考察点你能不能抓住输入数据的特性来设计算法而不是上来就无脑套用哈希表。能把“因为有序所以重复必相邻”这句话在面试开头说出来基本已经赢了一半。2. 双指针解法的完整推导2.1 先写暴力解法才知道优化在哪最容易想到的暴力做法是这样的从第二个元素开始往后扫如果发现当前元素和上一个保留的元素相同就把后面所有元素整体往前挪一格同时把数组长度减一。这个做法的时间复杂度最坏是 O(n²)。比如数组全是同一个数每看到一个重复元素都要搬移后面剩余的所有元素数据量稍微大一点就卡得没法看。而且一边遍历一边搬移下标管理很容易出乱子写出来往往还要调试半天。暴力解法的意义不是让你用它交作业而是帮你看清楚慢在哪里。慢就慢在“真的删除了元素”而实际上我们根本不需要删除只需要把不重复的元素按顺序挪到前面。这个认知转变就是双指针的入口。2.2 快慢指针的操作过程双指针的核心是让两个指针各司其职慢指针 i 指向“当前已经确认的最后一个不重复元素”快指针 j 负责往前探索。初始时 i 0因为第一个元素必然保留。j 从 1 开始遍历每次比较 nums[j] 和 nums[i]。如果两者相等说明 j 指向的还是重复元素什么都不做j 继续往前走。如果两者不相等说明找到了一个新的不重复元素。先把 i 往右挪一位空出位置再把 nums[j] 拷贝到 nums[i] 上。等 j 把整个数组扫完nums[0..i] 就是去重后的结果返回 i 1 就是新长度。拿一个经典例子手跑一遍数组是 [0,0,1,1,1,2,2,3,3,4]快指针 jnums[j]和 nums[i] 比较操作后 i数组前几位10等于 nums[0]00021不等于 nums[0]01写入 nums[1]10,131等于 nums[1]110,141等于 nums[1]110,152不等于 nums[1]12写入 nums[2]20,1,262等于 nums[2]220,1,273不等于 nums[2]23写入 nums[3]30,1,2,383等于 nums[3]330,1,2,394不等于 nums[3]34写入 nums[4]40,1,2,3,4最后返回 5数组前五位是 0,1,2,3,4任务完成。2.3 正确性与复杂度论证很多人代码背下来了但被问“为什么这样写就是对的”就卡住。这里的关键论断是因为数组有序所有值为 x 的元素都连续排列。当快指针发现一个和 nums[i] 不同的值 y 时y 一定比 nums[i] 大而且是从未出现过的下一个新值。放到 i1 的位置不会覆盖任何还需要保留的元素。更严谨一点可以用不变式来理解处理完快指针 j 之前的所有元素后nums[0..i] 始终是原数组前 j1 个元素的去重结果。初始化时 j0、i0显然成立。每次迭代如果 nums[j] 等于 nums[i]去重结果不变如果不等于nums[j] 一定是新值写入 i1 处后 nums[0..i1] 仍然是去重结果。j 走完整个数组时nums[0..i] 就是完整去重结果。复杂度也简单每个元素恰好被快指针访问一次比较和赋值都是常数时间所以时间复杂度 O(n)。额外只用了两个整数变量空间复杂度 O(1)。这个复杂度要能脱口而出面试官很爱问。3. 代码实现的细节与坑3.1 四种主流语言的标准实现先说 Python 版本这也是我平时写得最多的def removeDuplicates(nums): if not nums: return 0 i 0 for j in range(1, len(nums)): if nums[j] ! nums[i]: i 1 nums[i] nums[j] return i 1C 版本要注意 vector 的 size 类型避免无符号数和 int 比较带来的警告int removeDuplicates(vectorint nums) { if (nums.empty()) return 0; int i 0; for (int j 1; j (int)nums.size(); j) { if (nums[j] ! nums[i]) { i; nums[i] nums[j]; } } return i 1; }Java 和 C 几乎一样public int removeDuplicates(int[] nums) { if (nums.length 0) return 0; int i 0; for (int j 1; j nums.length; j) { if (nums[j] ! nums[i]) { i; nums[i] nums[j]; } } return i 1; }JavaScript 版本主要注意函数签名和空数组判断var removeDuplicates function(nums) { if (nums.length 0) return 0; let i 0; for (let j 1; j nums.length; j) { if (nums[j] ! nums[i]) { i; nums[i] nums[j]; } } return i 1; };四个版本逻辑完全一致区别只在语法。建议至少熟悉两门语言面试时用最顺手的写但心里要能用另一门语言翻译一遍。3.2 四类边界条件必须提前跑一遍写完之后我会习惯性在脑子里过这几个测试用例基本能覆盖所有实现错误空数组 []循环不执行直接返回 0。如果这里返回 1就崩了。单元素数组 [5]快指针不会进入循环返回 1。全部相同 [7,7,7]每个 j 都和 nums[0] 相等i 一直是 0返回 1。全部不同 [1,2,3,4]每个 j 都会触发一次赋值数组不变返回 4。混合情况 [0,0,1,1,1,2,2,3,3,4]返回 5前五位正确。负数情况 [-2,-2,-1,0,0,1]逻辑不受影响返回 4。我见过不少人在“空数组返回 0”上翻车就是因为没有养成先判空的习惯。这个小细节在面试考场上特别显眼。3.3 为什么不需要清理数组后面的残留这个问题业务背景强的读者可能会疑惑既然“删除”了为什么 nums[5] 之后还留着旧值答案是接口的约定。这道题的本质是 C 风格 API返回一个有效长度 k调用方只关心前 k 个位置。想象一个固定大小的数组结构去重逻辑只要保证“有效长度”正确后面的残留数据会在下一批写入时被自然覆盖。硬要清理反而画蛇添足还白白增加 O(n) 时间。如果被面试官追问“打印整个数组会看到什么”不用慌老实回答后半部分还是原来的旧值但对这个接口来说逻辑长度是 k所以没人会读它。如果面试官要求“物理上把后面也清掉”那是另一种约定再单独处理。4. 从一道题看到一类题4.1 变体一保留最多 k 个重复元素去掉“只保留一个”的限制改成“每个元素最多保留 k 个”就是另一道高频题删除有序数组中的重复项 II典型 k2。其实有一个非常优雅的通用写法def removeDuplicatesK(nums, k): i 0 for x in nums: if i k or nums[i - k] ! x: nums[i] x i 1 return i核心逻辑就一句话i 表示下一个可写位置。当 i k 时结果里还没积累够 k 个任何元素都直接写入。当 i k 时需要判断当前元素 x 是不是已经出现了 k 次只需要看 nums[i - k] 是否等于 x 即可。为什么看 nums[i-k] 就够了因为 nums[0..i-1] 是已经处理过的去重结果如果 x 在里面出现了至少 k 次那么由于有序性第 i-k 个位置必然也是 x。反过来如果 nums[i-k] ! x说明 x 出现次数不足 k 次这次可以放心写入。拿 [1,1,1,2,2,3]、k2 走一遍x1i0 2写入i1x1i1 2写入i2x1i2nums[0]1 1跳过x2i2nums[0]1 ! 2写入i3x2i3nums[1]1 ! 2写入i4x3i4nums[2]1 ! 3写入i5返回 5数组前五位是 [1,1,2,2,3]。这个写法的妙处是当 k1 时它就退化成原题。背一个通用模板等于同时掌握了三道题。4.2 变体二无序数组的去重怎么处理面试官如果把题改成“无序数组”有序解法就失效了。这时按约束强弱有完全不同的分支允许重新排序先快排时间 O(n log n)再用双指针。工程上很常用因为排序后还能顺便做别的事。不允许排序但允许额外空间用一个哈希集合记录哪些值出现过双指针扫一遍没出现过的写入并加入集合。时间 O(n)空间 O(n)。既不允许排序也不允许额外空间最差只能 O(n²)每来一个新元素回头在 nums[0..i-1] 里查一遍是否出现过。这三种路径要能脱口而出。面试官特别爱在这种地方追一句“如果把有序条件去掉你怎么做”答不上来会显得只会背模板。4.3 变体三流式数据的去重真实业务里很多时候遇到的不是静态数组而是一条一条进来的数据流。如果数据无序最简单的方案是维护一个集合seen set() for x in data: if x not in seen: seen.add(x) result.append(x)如果数据流本身就是有序的那更省只需要记住上一个输出值last None first True for x in data: if first or x ! last: result.append(x) last x first False这就是有序性带来的红利连哈希表的空间都省了。日志按时间戳去重、消息队列里相邻重试消息的过滤都是这个思路。4.4 变体四有序链表去重数组换成同一个思路链表版也常被拿来考尤其是面试后端岗的时候。区别在于链表没有“覆盖写”只能改 next 指针def deleteDuplicates(head): cur head while cur is not None and cur.next is not None: if cur.val cur.next.val: cur.next cur.next.next else: cur cur.next return head注意两个细节判断条件里必须先判 cur 再判 cur.next防止空指针发现重复时 cur 不要动继续比较新 next 节点与当前节点直到不相等才前进。链表版如果再加上“保留最多 k 个”的条件就要引入计数器或者递归复杂度会上一个台阶。5. 面试与工程实战经验5.1 面试官想听的答题路径这道题的代码很短真正拉差距的是答题姿势。我自己的建议是先说思路、再写代码顺序大概是确认条件“数组有序重复元素连续对吧”讲方案“我用快慢指针慢指针指向去重结果的末尾快指针遍历整个数组发现新值就放到慢指针后面。”说明边界“空数组返回 0单元素返回 1。”最后动手写。很多人一上来就低头写写完代码再解释这其实错过了展示沟通能力的机会。面试官看着是让写代码实际上更想看到你能不能把一个模糊问题拆清楚。代码写完后再主动说一句“这个算法时间复杂度 O(n)空间复杂度 O(1)只用了两个整数变量”。这一句话就能把整道题的收尾做得非常漂亮。5.2 工程中类似的去重场景说句实话这道题的真面目就是业务里最常见的那类去重需求。我自己在实际项目里遇到过好几个对应场景按时间戳排序的日志需要去重并且保留最后一条可以从右往左做双指针逻辑镜像对称。数据库导出的 ID 列表已经按主键排好序客户端本地去重用双指针避免把几百万条数据全部塞进集合再转数组。两个有序数组合并时顺带去重归并逻辑里遇到相等只保留一个相当于双指针的加强版。数据管道里经过稳定排序的数据流下游去重时只要记住上一个值。有一个工程教训我印象很深某次同事图省事把有序数组转成了集合再转回列表。结果是没错但一方面白白多占了一倍内存另一方面在某些语言里集合不保证顺序原本有序的数据被搞乱了。这要是数据量再大一点线上事故就来了。5.3 常见错误自查表我把新手容易踩的坑整理成了一张表每次写这道题之前扫一眼错误表现原因正确做法空数组返回 1没处理长度为 0 的情况先判空返回 0循环里调用删除接口误解“删除”语义用赋值覆盖不真的删赋值前忘记 i会把新值写到已保留的位置上先 i再 nums[i]nums[j]返回 i 而不是 i1忘了慢指针从 0 开始长度是 i1只测一个用例就交卷边界覆盖不足全等、全异、空、单元素都跑一遍用相邻比较后边删边遍历下标移位导致漏数据用慢指针维护写入位置第六个坑特别隐蔽。有些人会写成“if nums[j] ! nums[j-1] 就保留”然后直接在原数组上做删除边遍历边删下标一乱就蹦出奇怪结果。正确的做法是始终让慢指针 i 指向“已保留区间的最后一个元素”别去依赖快指针的前一个位置。5.4 一个面试追问的加分回答面试官还喜欢问“为什么这里比较的是 nums[j] 和 nums[i]而不是 nums[j] 和 nums[j-1]”这个问题答好了非常加分。标准答案是nums[i] 是去重结果里最后一个被保留的元素而 nums[j-1] 可能是一个已经被跳过的重复值。虽然因为有序性在很多例子里比较 nums[j-1] 也能判断新值但一旦需要维护“覆盖写入”的位置慢指针 i 才是唯一可靠的参照物。更重要的是这套以 i 为参照的写法可以直接推广到“保留 k 个”的通用解法里而相邻比较的写法扩展性很差。换句话说比较 nums[i] 不只是写对了这道题还为后面的变体铺好了路。这种“解法有延展性”的意识是区分刷题者和工程师的一个明显标志。5.5 一点个人心得最后说点我自己的经验。每次带新人练这道题我都让他们别急着看题解先在纸上用 [0,0,1,1,1,2,2,3,3,4] 把双指针完整走一遍。慢指针画成竖线快指针画成箭头每走一步都写下两个指针的位置。做完这一遍基本就不会再写错下标了。还有一个小技巧是检查 return。凡是返回数组长度的题目写完之后立刻盯住 return 那一行问自己空数组走到这里会返回什么如果答案是 0边界就稳了。这道题真正想训练的并不是记住双指针而是养成“先抓输入特性、再选数据结构、最后落实边界”的习惯。这个习惯带去哪家公司、做什么项目都不过时。