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

题目描述

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 说明： 为什么返回数值是整数，但输出的答案是数组呢？ 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 你可以想象内部操作如下: // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝 int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); } 示例 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 。 不需要考虑数组中超出新长度后面的元素。

提示： 1 <= nums.length <= 3 * 10^4 -104 <= nums[i] <= 10^4 nums 已按升序排列

题目解析

题目在说什么

简单来说，这道题给你一个已经排好序的数组（从小到大），让你“原地”修改它，把那些出现次数超过2次的数字删掉，只保留最多2次。最后返回修改后数组的长度。

比如，数组是 [1,1,1,2,2,3]，里面1出现了3次，超过2次了，所以我们只保留两个1，变成 [1,1,2,2,3]，长度是5。

注意“原地”的意思：你不能新建一个数组来存结果，必须直接在原来的数组上改。而且只关心前几个元素（长度以内）是对的，后面的元素不管它。

思路是怎么来的

想象一下，你有一个长长的书架，上面摆满了书，每本书都有编号，而且编号从小到大排好了。现在你要整理书架：每种编号的书最多只能放两本，多的要拿走。但是你不能把书都搬下来再重新摆，只能在书架上直接调整。

你会怎么做？一种自然的想法是：拿两个手指头，一个手指（慢指针）指向你最终要放书的位置，另一个手指（快指针）在书架上往前扫描，检查每一本书。如果这本书是新的编号，或者这个编号已经出现但不超过两次，你就把它放到慢指针的位置，然后两个手指都往前挪一步。如果这本书已经出现两次了，你就跳过它，只动快手指。

这个“慢指针”就像是你在书架上预留的空位，等着放合格的书。“快指针”就是你的眼睛，一路看过去，判断哪本书可以放进来。

具体到这道题，因为数组是有序的，所以相同的数字都挤在一起。我们只需要记住当前数字出现了几次，如果还没到两次，就可以保留；如果已经两次了，后面的相同数字就全部跳过。

代码逐步拆解

我们来看一个常见的写法（用Python，但思路通用）：

def removeDuplicates(nums):
    # 如果数组长度小于等于2，直接返回原长度，因为最多重复两次
    if len(nums) <= 2:
        return len(nums)
    
    # slow 是慢指针，指向下一个可以放元素的位置
    # 因为前两个元素肯定可以保留（即使重复也只到两次），所以从第3个位置开始考虑
    slow = 2
    
    # fast 是快指针，从第3个元素开始扫描（索引2）
    for fast in range(2, len(nums)):
        # 关键判断：如果当前元素 nums[fast] 不等于 slow-2 位置的元素
        # 说明这个数字还没出现两次（因为有序，所以相同数字连续）
        if nums[fast] != nums[slow - 2]:
            nums[slow] = nums[fast]
            slow += 1
        # 如果相等，说明这个数字已经出现两次了，跳过，不保留
    
    return slow

逐步拆解：

1. 为什么前两个元素直接保留？ 因为每个数字最多出现两次，前两个元素无论是什么数字，都还没超过两次，所以直接保留。所以我们从索引2（第三个元素）开始处理。

2. slow = 2 是什么意思？ slow 指向的是下一个可以放合格元素的位置。一开始，前两个位置（索引0和1）已经放好了，所以下一个空位是索引2。

3. 循环从 fast = 2 开始 fast 从索引2开始，逐个检查每个元素。

4. 关键判断：`nums[fast] != nums[slow - 2]` 这是最巧妙的地方。因为数组有序，相同的数字都挨着。slow - 2 指向的是当前已经保留的序列中，倒数第二个位置。

• 如果 nums[fast] 和它相等，说明这个数字已经出现了两次（因为慢指针前面已经有两个相同的了），所以这个新来的相同数字就不能再要了。
• 如果不相等，说明这是一个新的数字（或者虽然和前面相同，但前面只出现了一次，现在第二次出现），所以可以保留。