面试经典150题[004]：删除有序数组中的重复项 II（LeetCode 80）

删除有序数组中的重复项 II（LeetCode 80）

题目链接：80. 删除有序数组中的重复项 II
难度：中等

1. 题目描述

给定一个 已排序 的整数数组 nums，请 原地 删除重复出现的数字，使每个元素最多出现 两次，返回删除后数组的新长度。
要求：

• 不使用额外数组空间（O(1) 空间）
• 原地修改数组

示例：

输入: nums = [1,1,1,2,2,3]
输出: 5, nums = [1,1,2,2,3,_,_]

2. 问题分析

2.1 规律

• 数组是 有序的，所以重复元素一定是连续出现。
• 如果允许每个数字最多出现 m 次（本题 m=2），那么超过这个次数的元素要被跳过。
• 核心问题：如何判断当前元素是否已经出现过 m 次？

2.2 双指针思路

我们用两个指针：

• slow（慢指针）：指向结果数组的下一个可写位置，也就是当前等待赋值的位置，它左侧的内容都是处理完的哦。
• fast（快指针）：遍历整个数组用。

2.3 判断条件：

• 前 m 个元素无条件保留（因为它们不可能重复超过 m 次）。
• slow和fast都从第 m+1 个元素开始，注意这里第m+1个元素 == 从0开始的m索引，也就是从索引m开始哦。
  • 如果 nums[fast] != nums[slow - m]，则说明当前元素没有超过 m 次，可以写入。
  • 否则跳过。

2.4 核心判断公式

允许出现 m 次时：

if nums[fast] != nums[slow - 2]:nums[slow] = nums[fast]slow += 1

2.5 为什么是 nums[slow - m]？

• slow 指向的是下一个可写位置，即当前等待赋值的位置。
• slow 之前的部分已经是“符合条件的去重结果”。
• 那么当 fast 扫描到一个新元素时，我们要判断:
  • 如果它和 slow 前面 m 个位置的元素相等，因为数组是递增的，说明从前面m个位置到fast位置都是一样的值，那么它已经出现了 m 次，不能再加进去了。
  • 如果不相等，说明这个元素的出现次数 还没超 m 次，可以加进结果。

3. 代码实现

Python

class Solution(object):def removeDuplicates(self, nums):if len(nums) <= 2:return len(nums)slow = 2  # 从第3个位置开始检查for fast in range(2, len(nums)):if nums[fast] != nums[slow - 2]:nums[slow] = nums[fast]slow += 1return slow

C++

class Solution {
public:int removeDuplicates(vector<int>& nums) {int m = 2; // 最多允许重复次数int n = nums.size();if (n <= m) return n; // 如果长度小于等于 m，直接返回int slow = m; // 从第 m 个位置开始for (int fast = m; fast < n; fast++) {// 核心判断：当前数和 slow-m 位置的数不相等，说明还没超出重复限制if (nums[fast] != nums[slow - m]) {nums[slow] = nums[fast];slow++;}}return slow;}
};

4. 复杂度分析

• 时间复杂度：O(n)，只遍历一次数组，每个元素最多被比较一次
• 空间复杂度：O(1)，原地修改，不使用额外数组

5. 总结

• 已排序数组 + 限制出现次数 → 双指针是首选
• 核心判断 nums[fast] != nums[slow - m] 很通用
  • m=1 → LeetCode 26（经典去重）
  • m=2 → 本题
  • m=n → 保留任意次数

复习

面试经典150题[003]：26. 删除有序数组中的重复项