当前位置：首页 > news >正文

LeetCode 80：删除排序数组中的重复项 II | 双指针进阶应用

news 2026/5/22 2:06:40

LeetCode 80：删除排序数组中的重复项 II | 双指针进阶应用

引言

删除排序数组中的重复项 II（Remove Duplicates from Sorted Array II）是 LeetCode 第 80 题，属于 Medium 难度，是删除排序数组中重复项的进阶版本。题目要求在原地修改数组，使得每个元素最多出现两次。与简单版本（每个元素最多出现一次）不同，这个进阶版本需要我们仔细处理重复次数的限制，考察对双指针技巧的深入理解。

这道题的核心挑战在于如何在不使用额外空间的情况下，将重复超过两次的元素从数组中移除。由于输入数组是排序的，相同的元素会聚集在一起，这为双指针法的应用提供了便利条件。通过合理设计指针移动策略和边界条件处理，我们可以在单次遍历中完成去重任务。

问题分析

题目描述

给定一个排序数组 nums，原地删除重复出现的元素，使得每个元素最多出现两次。返回删除后数组的新长度。不要使用额外的数组空间，必须在原地修改输入数组并在 O(1) 额外空间下运行。例如输入 [1,1,1,2,2,3]，删除后数组变为 [1,1,2,2,3]，新长度为 5。

问题特点

这个问题有几个显著特点需要特别注意。首先是"原地修改"的要求，意味着我们不能创建新的数组来存储结果，必须在原数组上进行操作。其次是"最多出现两次"的限制，这比简单版本（最多出现一次）更为复杂，因为我们需要区分一个元素是第一次出现还是第二次出现。最后是排序数组的前提条件，这使得相同元素必然相邻，为双指针法提供了应用基础。

理解"最多出现两次"的含义至关重要。每个元素可以保留两次，但如果有超过两个的相同元素，多余的部分必须被删除。在保留的两个中，哪个位置保留、哪个位置删除是需要仔细考虑的问题。通常的策略是保留第一次和第二次出现的位置，将后续的重复都删除。

与简单版本的对比

LeetCode 第 26 题是简单版本，要求每个元素最多出现一次。简单版本的解法相对直接：遍历数组，当发现当前元素与前一元素不同时，将其移动到结果位置。由于只需要保留一个，我们可以简单地用快指针遍历数组，遇到新元素就将其复制到慢指针位置。

对于最多出现两次的版本，情况会更加复杂。我们需要记录当前元素已经出现了多少次，当第三次出现时开始删除操作。这增加了状态追踪的复杂性，也是本题的难点所在。

双指针法设计

指针角色定义

在解决这个问题的双指针法中，我们定义两个指针：slow 指针指向当前已处理部分（无重复或重复符合要求）的最后一个位置，fast 指针用于遍历整个数组。初始时，slow 指向数组开头（对于非空数组），fast 也指向开头。

算法维护一个关键信息：当前处理的元素已经出现了多少次。由于数组是排序的，当遇到与 nums[slow] 相同的元素时，说明这是重复元素。在简单版本中，一旦遇到不同的元素就直接处理；在进阶版本中，我们需要额外判断这已经是第几次出现。

处理逻辑

def removeDuplicates(nums): if len(nums) <= 2: return len(nums) slow = 0 count = 1 for fast in range(1, len(nums)): if nums[fast] == nums[slow]: if count < 2: count += 1 slow += 1 nums[slow] = nums[fast] else: slow += 1 nums[slow] = nums[fast] count = 1 return slow + 1

这段代码展示了双指针法的核心逻辑。当 fast 指向的元素与 nums[slow] 相同时，说明遇到了重复元素。此时如果 count 小于 2（即该元素还没有保留够两次），我们可以将 fast 位置的元素复制到 slow+1 位置，并增加计数。当遇到不同元素时，说明开始处理新的元素，需要将计数重置为 1，并将新元素复制到 slow+1 位置。

优化版本

上述实现虽然正确，但还有一个更优雅的版本，直接基于元素出现次数的判断：

def removeDuplicates_optimized(nums): if len(nums) <= 2: return len(nums) slow = 2 for fast in range(2, len(nums)): if nums[fast] != nums[slow - 2]: nums[slow] = nums[fast] slow += 1 return slow

这个优化版本更加简洁。其核心思想是：对于最多出现两次的要求，在位置 slow 处的元素只需要保证它与 slow-2 位置的元素不同即可。因为 slow-2 是 slow 位置前两个位置的元素，如果当前元素与 slow-2 相同，说明这是第三个或更后的重复元素，应该被跳过；如果不同，说明要么是新的元素，要么是第一个或第二个重复，可以保留。

代码实现详解

边界情况处理

首先需要处理数组长度小于等于 2 的情况。对于这样的短数组，无论是否存在重复，每个元素都可以保留（因为最多只需要两个），因此直接返回原数组长度即可。这是代码中第一个 if 语句的作用。

if len(nums) <= 2: return len(nums)

主循环逻辑

主循环从索引 2 开始，这是因为前两个元素无论是否相同都可以保留（最多出现两次的限制对前两个元素没有影响）。对于索引小于 2 的位置，我们不需要任何判断，直接保留原值即可。

循环中，每次检查 nums[fast] 是否与 nums[slow-2] 相同。这里的 slow-2 是关键：它代表在已处理部分中，可能与当前 fast 位置元素重复的最近位置。由于我们只允许每个元素最多出现两次，如果当前元素与 slow-2 位置的元素相同，就说明这是第三个（或更后的）重复，应该被跳过。

复制与更新

当条件满足时（即当前元素与 slow-2 位置的元素不同），我们将 nums[fast] 复制到 nums[slow] 位置，然后将 slow 加 1。这个复制操作实际上是将"保留"的元素移动到正确的位置。由于 fast 总是向前移动，这个过程保证了每个元素最多被检查一次，时间复杂度为 O(n)。

算法复杂度分析

时间复杂度

双指针法的时间复杂度为 O(n)，其中 n 是数组长度。fast 指针遍历整个数组一次，每次循环只进行常数次的操作（比较和可能的赋值）。虽然内层没有循环，但由于 fast 和 slow 最多都只移动 n 次，整体时间复杂度仍然是线性的。

空间复杂度

算法的空间复杂度为 O(1)，只使用了两个指针变量和少量辅助变量。这满足了题目"必须在 O(1) 额外空间下运行"的要求。无论输入数组有多长，额外的内存使用始终是常数级别的。

更一般化的问题

K次重复限制

将问题扩展到每个元素最多出现 K 次是很自然的。首先考虑如何修改代码以支持任意的 K 值：

def removeDuplicatesK(nums, k): if len(nums) <= k: return len(nums) slow = k for fast in range(k, len(nums)): if nums[fast] != nums[slow - k]: nums[slow] = nums[fast] slow += 1 return slow

这个通用版本中，我们将判断条件从 nums[slow-2] 改为 nums[slow-k]，将初始的 slow 值从 2 改为 k。这样，对于 K=1 的情况，就变成了简单版本（每个元素最多出现一次）；对于 K=2 的情况，就是本题的版本。

时间空间权衡

上述方法在时间上是最优的 O(n)，空间上是 O(1)。如果允许额外的空间，我们可以使用哈希表来计数每个元素出现的次数，然后重新构建数组。但哈希表方法需要 O(n) 的额外空间，在空间受限的场景下不如双指针法优雅。

测试用例

def test_remove_duplicates(): nums1 = [1, 1, 1, 2, 2, 3] assert removeDuplicates(nums1) == 5 assert nums1[:5] == [1, 1, 2, 2, 3] nums2 = [0, 0, 1, 1, 1, 1, 2, 3, 3] assert removeDuplicates(nums2) == 7 assert nums2[:7] == [0, 0, 1, 1, 2, 3, 3] nums3 = [1, 1, 1] assert removeDuplicates(nums3) == 2 nums4 = [1, 2, 3] assert removeDuplicates(nums4) == 3 nums5 = [] assert removeDuplicates(nums5) == 0 nums6 = [1, 1] assert removeDuplicates(nums6) == 2 print("所有测试用例通过！")