80. 删除有序数组中的重复项 II

题意

给你一个有序数组 nums ，请你原地 删除重复出现的元素，使得出现次数超过两次的元

素只出现两次 ，返回删除后数组的新长度。

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

下完成。

难度

中等

示例

示例 1：

输入：nums = [1,1,1,2,2,3]

输出：5, nums = [1,1,2,2,3]

解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需

要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]

输出：7, nums = [0,0,1,1,2,3,3]

解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。

不需要考虑数组中超出新长度后面的元素。

分析

这道题很容易让我们联想到 026.删除有序数组中的重复项 ，当时我们使用的是暴力算

法，先解出答案再说，因为 026.删除有序数组中的重复项 的条件限制比较严格，很难直

接采用双指针的算法，今天这道题，我们打算试试双指针。

• 双指针算法使用两个指针在数据结构中遍历，如数组或链表。这种方法可以有效减少

时间和空间复杂度。

• 暴力算法，也被称为朴素算法，是解决问题的一种简单直接的方法。其基本思路是先

把题解出来再说，不考虑时间和空间复杂度。

首先我们来观察数组长度较小的情况下，我们应该如何解题。

如果 nums.length <= 2，那么我们就不需要考虑如何处理，直接返回原数组的长度即

可，因为如果存在重复项，最多也只可能出现两次。

如果 nums.length == 3，我们只需要判断 nums[2]和 nums[0]是否相等即可，因为二者

如果相等，按照有序数组这一特性，我们可以确定 nums[0],nums[1],nums[2]就是相等

的元素，直接除掉 nums[2]返回就行了。

推算到到这一步，我们就可以将整个 nums 分为已检查区、检查区/排除区和未检查区来

套用上面的策略。

在上述例子中，nums.length 小于 2 的情况下，我们均不用对里面的元素进行检查，或者

说，已经利用规则将其自动检查了，当 nums.length 等于 3 的情况下，我们也不用对

nums[0],nums[1]进行检查，只需要排除第 3 个元素即可。

其实到这一步，我们的算法雏形已经浮现出来了，采取两个指针 lef,rig，开始都指向 2 的

位置，然后我们把整个 nums[]分割成已检查区 和 未检查区，[0-(lef-1)]的区域为已检查

区，[rig-(n-1)]为未检查区。

接下来，我们的任务就是保证已检查区内的元素个数不能超过 2。

我们向后移动 rig，并且对这时的 nums[rig]进行检查，如果这时候 nums[rig] ==

nums[lef - 2]，我们就必须舍去 nums[rig]，因为如果 nums[rig] == nums[lef - 2]，根

据数列有序的这一特性，则 nums[lef - 1] == nums[lef - 2]，这样子就必然会有三个一

样的数字出现，所以我们舍去 nums[rig]，向后移动**rig**。

那如果 nums[rig] != nums[lef - 2]呢？

这时候我们就要将这个新的元素纳入已检查区了，因为这表示已检查区最多也就只有一个

跟 nums[rig]相等的元素，所以我们就可以大胆地将其纳入已检查区。

最后的答案，自然就是已检查区的长度。

具体实现：

class Solution {

public int removeDuplicates(int[] nums) {

// 如果数组长度小于等于 2，则直接返回长度

if(nums.length <= 2)

return nums.length;

// checked 表示当前检查到的位置，也是下一个要放入的位置

// checking 表示当前正在检查的位置

int checked = 2, checking = 2;

// 遍历数组

while(checking < nums.length){

// 如果当前检查的数字和 checked 位置的前两个数字不同，

// 这意味着我们可以把这个数字放到 checked 位置

if(nums[checked - 2] != nums[checking]){

nums[checked] = nums[checking];

checked++;

}

// 无论是否复制数字，都向前移动 checking 指针

checking++;

}

// 返回新的数组长度

return checked;

 }

}

OK，来看解题效率：

080.%E5%88%A0%E9%99%A4%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E4

%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E9%A1%B9II-20230924075405.png

我们来模拟一下当前的解题过程。

题目的目标是删除有序数组中的重复项，但是每个元素最多可以出现两次。为了解决这个

问题，我们使用两个指针来遍历数组。

1. 指针 checked：指向应当被修改的位置。

2. 指针 checking：遍历数组，检查每个元素是否应当被复制到 checked 位置。

基本思路：

当 nums[checked - 2] != nums[checking] 时，表示当前 checking 所指向的元素与

checked 前两个元素不同，因此可以被复制。

图解：

假设我们的输入数组为:

nums = [1,1,1,2,2,3,3]

初始状态：

nums: 1 1 1 2 2 3 3

---------------------

pointers: c c

(此处 c 代表 checked 和 checking 都在此位置)

第一步：nums[checked - 2] 与 nums[checking] 相同，因此我们只移动 checking：

nums: 1 1 1 2 2 3 3

---------------------

pointers: c c

第二步：现在 nums[checked - 2] 与 nums[checking] 仍然相同，只移动 checking：

nums: 1 1 1 2 2 3 3

---------------------

pointers: c c

第三步：现在 nums[checked - 2] 与 nums[checking] 不同，复制元素：

nums: 1 1 2 2 2 3 3

---------------------

pointers: c c

按照这样的方式继续，直到 checking 到达数组末尾。

最终：

nums: 1 1 2 2 3 3 3

---------------------

pointers: c c

返回值为 checked 的值：5，表示有效的元素为[1,1,2,2,3]。

总结

本题主要还是双指针算法的运用，利用双指针法可以巧妙的将整个 nums 分开，从而保证

已检查区内的每个元素的数量不超过 2。

力扣链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array-

ii/

更新: 2023-09-24 00:16:04

原文: https://www.yuque.com/itwanger/czfoq9/dtbrhv