删除有序数组中的重复项 II
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个有序数组 nums，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
请注意，输入数组是以「引用」方式传递的：函数返回的长度 k 表示 nums 的前 k 个元素为修改后的有效结果，超出部分可忽略。
示例 1
示例 2
模拟答题者思考
1. 暴力想法：用哈希表统计每个数出现次数，再开新数组按序填入、每个数最多写两次——正确但 O(n) 额外空间，不符合原地 O(1) 要求。
2. 和 #26「每个数只留一次」的关系：本题是「每个数最多留两次」。#26 用 nums[fast] != nums[slow] 判断新值；这里需要判断「当前值是否还能再写一次」。
3. 有序性：相同数字在数组中连续。若结果前缀 nums[0..slow-1] 里某值已出现 2 次，则这 2 次一定占据末尾两个位置，且与即将扫描的 nums[fast] 相等时，nums[slow-2] 必然等于 nums[fast]。
4. 写入条件：前两个位置直接写（slow < 2）；否则仅当 nums[fast] != nums[slow-2] 时写入——等价于「该值在前缀里还不到 2 次，或 nums[fast] 是更大的新值」。
5. 一遍扫描，每个下标常数工作，返回 slow。与 #26 同属写指针 + 读指针，只是判等对象从 nums[slow] 换成 nums[slow-2]。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
slow | int | 定义：下一个待写入位置的下标，也是当前已保留元素个数；nums[0..slow-1] 为「每个值最多出现 2 次」的有效前缀维护：初始可视为空前缀，扫描时按需扩展；前两个位置无条件保留（任意值最多出现两次，前两位不可能超限） 更新：当判定 nums[fast] 可写入时，执行 nums[slow] = nums[fast]; slow++ |
fast | int | 定义：从左到右扫描原数组的读指针 维护：每轮用 nums[fast] 与结果区中「倒数第二个」元素比较，判断是否还能再保留一份相同值更新：每轮循环末尾 fast++，直到遍历完整个数组 |
nums[slow-2]（比较锚点） | int | 定义：当 slow ≥ 2 时，有效前缀里「同一数值已出现次数是否已达 2」的判据：若 nums[fast] == nums[slow-2]，则再写入会形成第 3 个连续相同值维护：有序数组下，相同值在结果前缀中必然相邻，故看倒数第二个即可代表「该值已保留了几份」 更新：仅用于条件 slow < 2 or nums[fast] != nums[slow-2]，不单独维护变量 |
k（返回值） | int | 定义：去重（限 2 次）后的有效长度 维护：等于扫描结束后的 slow更新：循环结束后直接返回 slow |
落码步骤
1. 令 slow = 0，for fast in range(len(nums)) 扫描每个元素
2. 若 slow < 2 或 nums[fast] != nums[slow - 2]，说明允许保留 nums[fast]：执行 nums[slow] = nums[fast]，slow += 1
3. 否则跳过 nums[fast]（该值在前缀中已有 2 份）
4. 扫描结束，nums[0..slow-1] 为符合题意的数组，返回 slow
代码实现
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
slow = 0 # nums[0..slow-1] 为每个值最多出现 2 次的前缀
for fast in range(len(nums)):
if slow < 2 or nums[fast] != nums[slow - 2]:
nums[slow] = nums[fast]
slow += 1
return slowclass Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow = 0; // nums[0..slow-1] 为每个值最多出现 2 次的前缀
for (int fast = 0; fast < nums.size(); fast++) {
if (slow < 2 || nums[fast] != nums[slow - 2]) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
};
// 时间 O(n)，空间 O(1)复杂度分析
O(n)
O(1)
常见坑
误用 #26 的条件 nums[fast] != nums[slow]：那样每个数只保留 1 次，与「最多 2 次」不符。
比较下标写成 nums[slow-1]：只保证与紧邻前一个不同，仍可能写入第 3 个相同值（如 1,1,1 时会错误保留三个 1）。
返回值写成 slow - 1 或 slow + 1：本题 slow 本身就是已写入元素个数，应直接返回 slow（与 #26 的 slow+1 不同，因 #26 的 slow 是最后下标而非长度）。
必测边界 Case
nums = [1] → 1；nums = [1,2] → 2（始终满足 slow < 2，全部保留）
nums = [1,1,1,1,1] → 2, nums = [1,1,...]（第三个及以后的 1 被跳过）
nums = [0,0,1,1,1,1,2,3,3] → 7（四个 1 只保留两个，与示例 2 一致）