leetcode80：删除有序数组中的重复项 II（快慢指针法）

LeetCode 80 删除有序数组中的重复项 II，【难度：中等；通过率：63.5%】，这道题是 LeetCode 26 删除有序数组中的重复项 的进阶版，要求我们保留最多 两个重复的元素，同样可是接着使用 双指针-快慢指针法解决，并且我们通过此题，总结出一个 通用的模板，最终可以解决 删除有序数组中的重复 K 项的问题

一、 题目描述

给你一个有序数组 nums，请你原地删除重复出现的元素，使得每个元素最多出现两次，返回删除后数组的新长度

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

示例:

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3,_]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3

二、 核心思路：快慢指针

解决此类问题的核心武器是快慢指针。我们将数组逻辑上分为两部分：

• [0...slow-1]：这是我们处理好的、满足“最多重复两次”要求的新数组
• [slow...fast-1]：这是已经被 fast 指针扫描过，但被我们“抛弃”的元素
• [fast...n-1]：这是待探索的未知区域

指针职责：

• slow (慢指针)：作为“写入”指针，nums[slow] 是下一个将被覆盖的位置。slow 本身也代表了新数组的长度
• fast (快指针)：作为“读取”指针，nums[fast] 是当前正在考察的元素

我们的目标就是移动 fast 指针遍历整个数组，当遇到一个“合法”的元素时，就将它“写入”到 slow 指针的位置，然后 slow 前进一格

---

三、计数器辅助的快慢指针

一种非常直观的实现思路：通过一个额外的计数器来判断当前元素是否“合法”

代码实现-直观快慢指针

class Solution {/*** 使用快慢指针，并辅以一个 repeat 计数器来跟踪当前元素的重复次数* slow 指针永远指向下一个可以被覆盖的位置*/public int removeDuplicates(int[] nums) {if (nums.length <= 2) {return nums.length;}int slow = 1; // 新数组的构建从索引 1 开始int repeat = 1; // 记录当前元素的重复次数for (int fast = 1; fast < nums.length; fast++) {// 遇到重复元素if (nums[fast] == nums[fast - 1]) {repeat++;// 如果重复次数小于等于 2，则保留该元素if (repeat <= 2) {nums[slow++] = nums[fast];}// 如果 repeat > 2，则不移动 slow，fast 继续前进，相当于“跳过”了该元素} else { // 遇到新元素repeat = 1; // 重置计数器nums[slow++] = nums[fast]; // 保留新元素}}return slow;}
}

提交结果：

优缺点分析

• 优点：逻辑非常清晰易懂，通过 repeat 计数器，我们能准确地知道每个元素的重复情况，易于理解和调试

---

四、 深度拓展：更通用的快慢指针模板

我们甚至可以摆脱 repeat 计数器，让逻辑更简洁，也更具扩展性，总结出一个此类题通用模板

核心思想

我们换一个角度思考：fast 指针指向的元素 nums[fast] 什么时候应该被保留？

答案是：当 nums[fast] 与新数组 [0...slow-1] 的倒数第二个元素 nums[slow-2] 不相等 时

为什么是 slow-2？

• nums[slow-1] 是新数组的最后一个元素
• nums[slow-2] 是新数组的倒数第二个元素
• 如果 nums[fast] 和 nums[slow-2] 相等，那么 nums[slow-1] 必然也和它们相等，因为：数组有序（题目给的条件），即 nums[fast] 将是第三个重复的元素，应该被抛弃
• 反之，如果 nums[fast] 和 nums[slow-2] 不相等，那么 nums[fast] 最多只是第二个重复的元素，应该被保留

我们还需要处理一个边界情况：当 slow < 2 时，新数组的长度还不足 2，此时任何元素都应该被无条件保留

代码实现-通用模板

class Solution {public int removeDuplicates(int[] nums) {if (nums.length <= 2) {return nums.length;}int slow = 2; // 新数组的前两个元素 [0, 1] 默认保留for (int fast = 2; fast < nums.length; fast++) {// 检查 fast 指向的元素是否应该被保留// 如果 nums[fast] 不等于新数组的倒数第二个元素 nums[slow-2]// 说明 nums[fast] 不是第三个重复元素，可以保留if (nums[fast] != nums[slow - 2]) {nums[slow] = nums[fast];slow++;}}return slow;}
}

提交结果：

优缺点分析

• 优点：
  • 代码更简洁，没有额外的状态变量
  • 扩展性极强：如果题目改成“最多保留 k 个重复项”，我们只需将 2 替换为 k 即可：if (slow < k || nums[fast] != nums[slow - k])。这是一个非常强大的通用模板
• 缺点：逻辑相对抽象，需要深刻理解 slow-2 的含义，以及为什么可以这样：题目说是有序的

---

五、 总结

	解法一 (计数器辅助)	解法二 (通用模板)
核心逻辑	通过 repeat 计数器判断是否保留	通过与 nums[slow-2] 比较来判断是否保留
状态变量	slow, fast, repeat	slow, fast
代码简洁性	中等	高
扩展性	需要修改 repeat <= 2 的判断	只需将 2 替换为 k 即可
时间/空间复杂度	O(N) / O(1)	O(N) / O(1)