• 文档
• 教程
• 知识库

本文是《InterviewGuide》精选力扣 300+ 道算法题系列中“双指针”标签下的一道 Medium 题解。围绕阿秀刷题笔记中的原始解法，从题目约束、引用传递机制、代码逐行拆解到复杂度论证，讲透“有序数组原地去重、每个元素最多保留两次”这一经典套路，并推广出可复用的“最多保留 k 次”通用模板，帮助你从容应对面试中的同族变体题。

题目回顾：LeetCode 80. 删除排序数组中的重复项 II

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

不要使用额外的数组空间，你必须在原地修改输入数组并在使用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 。 你不需要考虑数组中超出新长度后面的元素。

原笔记将其标注为“很好的题目”，原因在于：它表面是“删除重复元素”的简单任务，实则隐藏着双指针压缩、条件后移这两大高频面试考点，是 LeetCode 26. 删除排序数组中的重复项（每个元素最多保留一次）的升级版。

为什么返回的是整数，输出的却是数组？

题目说明中特别强调：输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。你可以想象内部操作如下：

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

这正是“原地（in-place）算法”的评测惯例：判题系统不关心数组尾部残留的旧数据，只按你返回的len截取前len个元素进行校验。因此解题时只需保证新序列紧挨在数组头部，超出新长度的部分可以任意残留，无需真正删除或缩容。

核心思路：一个“写指针”完成的原地压缩

对于已经排好序的数组，相同元素必然连续成段。要让每个元素最多出现两次，等价于：

扫描整个数组时，只要当前位置的元素不与“已保留序列中倒数第二个元素”相同，就可以安全地把它写入新序列的尾部。

这样整个数组只被扫描一遍，且就地写入，不需要开辟任何辅助数组，天然满足 O(1) 额外空间的要求。从实现形态上看，这属于双指针思想中“快慢指针”的变体——i是快指针（只读扫描），len是慢指针（写位置），两者共用同一个数组。

第一版解法（阿秀原解）：简洁到极致的双指针

原笔记给出的解法很短，执行用时 12 ms、内存消耗 8.9 MB（作者当时在 C++ 提交中的记录，分别击败约 98.85% 与 73.46% 的用户）：

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; }

原笔记参考了评论区大佬的解法，下面把各个步骤和变量的含义完整展开：

• len表示的是删除重复元素后新序列的长度，同时也表示新元素进入新序列的索引（即下一个写入位置）；
• i就是循环变量，用于遍历整个旧序列；
• if (len < 2) nums[len++] = nums[i];的意思是：如果新序列的长度小于 2（即新序列中不会存在两个相同的元素，此时i位置所在元素不可能与新序列中已有的两个元素构成三个相同元素），直接将新元素加入到新序列中，并更新新序列的长度；
• if (nums[i] != nums[len-2]) nums[len++] = nums[i];的意思是：如果新元素加入后不会和前两个元素构成 3 个相同的元素（nums[len-2]就是直接取新序列中倒数第二个元素，如果该元素和新元素相同，说明加入后会构成 3 个相同的元素，显然不符合题意），就将新元素加入到新序列中，并更新新序列的长度；
• 题意只要求将新序列紧挨在一起就行，多出的长度将不参与评测。

正确性论证：为什么这样写必然成立

可以分三步论证这段代码的正确性：

1. 前两个元素无条件保留。len < 2时直接写入，保证新序列长度至少为 2 前不受任何限制。因为一个元素出现两次总是被允许的，前两个元素无论相同与否都必然合法。
2. 从第三个元素起，只需与“倒数第二个”比较。由于数组有序且已保留的新序列同样有序，若nums[i]与nums[len-2]相同，则它必然也与nums[len-1]相同（中间夹着的元素只可能是同一个值），此时再写入就会形成 3 连重复，必须丢弃；反之，若与nums[len-2]不同，则无论与nums[len-1]是否相同，最多只会形成 2 连重复，写入后依然合法。
3. 写入位置len单调不减，且永远不会越过读取位置i（写入量 ≤ 读取量），因此覆盖操作是安全的，不会破坏后续待读取的数据。

复杂度分析

• 时间复杂度：O(n)。整个数组只被for循环扫描一遍，每次迭代仅做常数次比较与赋值，其中 n 为数组长度；
• 空间复杂度：O(1)。全程没有申请与 n 相关的辅助存储，仅使用了len、i两个整型变量，满足题目“不要使用额外的数组空间”的硬性约束。

这正是面试官期待的最优解：一趟扫描 + 常数空间，无法再被优化。

推广：把“最多两次”泛化成“最多 k 次”

从上面的正确性论证可以看出，比较基准nums[len-2]中的数字 2 正是题目允许的最大重复次数。把它替换成任意常数k，就得到“每个元素最多保留 k 次”的通用模板：

int removeDuplicates(vector<int>& nums, int k) { // k = 2 即本题 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时即本题。面试中只要讲清“为什么是与len-k位置比较”这一句，就能向面试官证明你吃透了这族题目的本质，而不是死记硬背代码。

从源码到面试：本专题的延伸阅读

• 本题收录于 InterviewGuide 仓库的 双指针专题目录（Medium 分组），聚合版题解可见 total/08-双指针/medium/medium.md；
• 同一专题下的 75. 颜色分类 同样是原地修改数组的代表题，其“第二版”用到了双路快排的思想，可与本题对照学习；
• 若想系统补齐数组原地操作与双指针的其他形态（相向指针、滑动窗口等），可先阅读仓库的 算法基础部分，再按 力扣刷题笔记专栏说明 中的 13 个标签逐个击破。

面试中遇到本题时，建议按“题目约束 → 有序性利用 → 写指针压缩 → 泛化到 k 次”这条链路作答，先说思路再写代码，最后补上复杂度分析，即可构成一次完整、扎实的算法面试回答。

• 文档
• 教程
• 知识库