InterviewGuide 刷题笔记：LeetCode 80 题《删除排序数组中的重复项 II》——双指针原地去重，允许每个元素最多出现两次

• 教程

导读

LeetCode 80 题「删除排序数组中的重复项 II」是面试高频的原地数组去重问题：给定一个已排序数组，要求删除重复元素、使每个元素最多出现两次，并返回新数组长度，全程只能使用 O(1) 额外空间。它是 26 题（每个元素最多一次）的进阶版，也是 InterviewGuide「精选力扣 300+ 题目之双指针」分类下的代表性中等题。读完本文，你将掌握快慢指针覆盖法的核心思想、nums[len-2]这一关键判断的底层原理，并能把解法推广到"每个元素最多保留 k 个"的通式，从容应对同类变体。

一、题目定位：它在 InterviewGuide 双指针体系中的位置

本题收录于 双指针题目分类目录，与 75. 颜色分类、56. 合并区间、424. 替换后的最长重复字符 等题同属一个刷题系列；原文档还单独收录了一份题目汇总版，见 双指针 medium 合集。

作者在文档标题中特别标注"很好的题目"，原因在于：它表面上是一道数组操作题，实际考察的是**快慢指针（双指针之一）**的经典应用——一个指针负责遍历原数组，另一个指针负责维护"去重后有效区间的写入位置"，两者配合即可做到一趟扫描、原地完成。

在动手之前，先明确两个贯穿全题的算法概念（InterviewGuide 在 算法基础篇 中有系统定义）：

• 原地修改：不申请额外存储空间，只利用原存储空间完成操作；
• 空间复杂度：运行完一个算法所需的内存大小，本题要求 O(1)。

二、题目描述与示例

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1：

给定 nums = [1,1,1,2,2,3], 函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 你不需要考虑数组中超出新长度后面的元素。

示例 2：

给定 nums = [0,0,1,1,1,1,2,3,3], 函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 你不需要考虑数组中超出新长度后面的元素。

（注：原文档示例 2 中"前五个元素"为笔误，实际返回长度为 7，应修改前 7 个元素。）

两个示例共同透露两个关键约束：

1. 返回值是整数（新长度），但判题系统会根据该长度打印数组前len个元素——所以前len个位置必须已经被整理为合法结果；
2. 超出新长度的尾部元素无需清理，这为"覆盖写入"（而不是"删除元素"）提供了合法性依据。

三、说明：为什么返回整数，输出却是数组？

原文档给出了官方说明的核心逻辑，这里完整保留并展开：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以**"引用"**方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下：

// nums 是以"引用"方式传递的。也就是说，不对实参做任何拷贝 int len = removeDuplicates(nums); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }

理解这一点对面试表达很重要：本题的"答案"由两部分构成——函数返回值（新长度）+ 被原地改写后的数组前段内容。判题系统先用返回的len界定打印范围，再按范围打印元素，二者缺一不可。这也是为什么许多候选人在 LeetCode 上写"复制一份新数组再返回"会直接超空间：题目要求的就是修改原数组，而不是生成新数组。

四、解法一：快慢指针覆盖法（原文档解法，逐行精讲）

原文档给出的解法非常精简，参考了评论区大佬的思路，直接贴出并逐行拆解：

int removeDuplicates(vector<int>& nums) { int len = 0; for (int i = 0; i < nums.size(); i++) { if (len < 2 || nums[i] != nums[len-2]) nums[len++] = nums[i]; } return len; }

4.1 变量含义（原文档详解，完整继承）

• len表示删除重复元素后新序列的长度，同时也表示新元素进入新序列的写入索引——它正是"慢指针"；
• i是循环变量，用于遍历整个旧序列——它正是"快指针"；
• if (len < 2) nums[len++] = nums[i];：如果新序列的长度小于 2（即新序列中不会存在两个相同的元素，此时i位置所在元素不可能与新序列构成"三个重复"），直接将新元素加入新序列并更新长度；
• if (nums[i] != nums[len-2]) nums[len++] = nums[i];：nums[len-2]直接取新序列中倒数第二个元素。若它与新元素相同，说明加入后会产生 3 个相同元素，违反"最多出现两次"的题意，故舍弃；若不同，则安全写入；
• 题意只要求新序列紧挨在一起即可，多出的长度不参与评测。

4.2 为什么用nums[len-2]而不是nums[len-1]？

这是本题最值得咀嚼的细节，也是面试官常追问的点：

• 若只比较nums[i] != nums[len-1]，能拦截的只是"与前一个元素相同"的情况，只能保证最多出现一次——那是 26 题的判定逻辑；
• 本题允许出现两次，因此需要把"窗口"再拉长一位，检查新序列倒数第二个元素。只要新元素与nums[len-2]不同，无论它与nums[len-1]是否相同（最多和倒数第一个相同），都不会造成三个连续相同元素。

换句话说，len永远指向"下一个可写位置"，而nums[len-2]恰好是"有效区间末尾往前数第二位"，用它做参照，天然把每个元素的保留上限卡死在 2 次。

4.3 手推一遍示例 1

以nums = [1,1,1,2,2,3]为例，逐步跟踪：

最终返回len = 5，数组前 5 位为[1,1,2,2,3]，与题目示例完全一致。可见快指针i读、慢指针len写，二者速度不同，是标准的快慢指针（读写指针）模型。

五、复杂度与正确性分析

• 时间复杂度 O(n)：i一趟扫描整个数组，循环体内是常数次比较与赋值，总操作次数与n = nums.size()成正比；
• 空间复杂度 O(1)：只使用了一个整型变量len，不申请任何与 n 相关的辅助数组，完全符合题目"原地 + O(1) 额外空间"的硬性要求；
• 正确性：len维护的始终是"已处理区间中满足每个元素最多出现两次的前缀"，通过数学归纳可知每一步写入都不会破坏该不变式，因此最终前缀即答案。

值得说明的是，原文档记录了作者当时的提交数据："执行用时 12 ms，在所有 cpp 提交中击败了 98.85% 的用户；内存消耗 8.9 MB，击败了 73.46% 的用户"。该数据属于特定提交环境下的历史记录，可作为参考，但不应作为跨平台、跨版本的普适结论。

六、举一反三：推广到"每个元素最多保留 k 个"

把判定条件中的常量 2 抽象为参数k，即可得到本题的通式解法：

int removeDuplicatesK(vector<int>& nums, int k) { int len = 0; for (int i = 0; i < nums.size(); i++) { if (len < k || nums[i] != nums[len - k]) nums[len++] = nums[i]; } return len; }

• k = 1时，退化为 LeetCode 26 题「删除排序数组中的重复项」（每个元素最多一次）；
• k = 2时，即本题 80 题；
• 任意k下，核心思想不变：只要新元素与"有效区间倒数第 k 个元素"不同，就允许写入。

面试中遇到此类题，可以先讲通式再代入 k=1/k=2，往往比直接背代码更显功底。作为对照练习，InterviewGuide 双指针分类下还有 532. 数组中的 K-diff 数对、75. 颜色分类（荷兰国旗问题）、986. 区间列表的交集 等同样考察双指针思想的题目，刷完本题后建议按序列继续巩固。

七、边界情况与易错点小结

1. 空数组与单元素数组：len < 2分支直接兜底，空数组返回 0、单元素返回 1，无需特判；
2. len-2的越界风险：仅在len >= 2时才会走到nums[i] != nums[len-2]分支（因为||短路），所以len-2 >= 0恒成立，索引安全——这正是"先判断len < 2"这一写法的精妙之处；
3. 不要用erase逐个删除：vector 中间删除是 O(n) 的，最坏会退化为 O(n²)，且同样破坏"原地"语义；覆盖写入才是本题最优姿势；
4. 返回值与数组前段要配套：只返回长度而忘记改写前len个元素，或者改了但返回错误的长度，都会导致评测失败；
5. 输入必须是已排序数组：题目前提是"排序数组"，若输入无序，解法不成立，需先排序再套用（InterviewGuide 在 十大排序 系列中整理了常用排序实现可供参考）。

八、总结

LeetCode 80 题的核心价值不在于"背下三行代码"，而在于它浓缩了三个面试高频考点：

1. 引用传递与原地修改：理解"返回值 + 被改写数组"共同构成答案，是很多企业笔试环境（如 ACM 式函数签名）下必须掌握的意识；
2. 快慢指针思想：i读、len写，一趟扫描完成去重，是数组类原地算法的通用范式；
3. 通过"倒数第 k 个元素"控制保留上限：把 26 题与 80 题统一到同一套通式，面对"最多保留 m 个"的任意变体都能立即迁移。

本文对应的原始题解记录位于 80.删除排序数组中的重复项II.md，刷题过程中建议结合 InterviewGuide 的 双指针专题目录 系统规划，把这一题当作"原地去重"系列的地基，理解透了，后续字符串去重、流式去重等变体都会迎刃而解。

• 教程