⚡Flashcard Drill➔
NeetCode #197LC-80MediumTwo Pointers
← Back to All Problems

#197 · #80 · Remove Duplicates from Sorted Array II(删除有序数组中的重复项 II)

📌 Problem Statement & Constraints

Given an integer array nums sorted in non-decreasing order, remove duplicates in place so that each unique element appears at most twice. Return the new length k; the first k slots must hold the result. Constraints: 1 <= nums.length <= 3 * 10^4, -10^4 <= nums[i] <= 10^4.

💡 Core Algorithmic Approaches

  1. Generalise the Remove Duplicates template: a write pointer k marks the next output slot.
  2. For each read element, write it only if it differs from the element two positions before the write pointer, i.e. nums[k-2].
  3. That comparison allows each value to appear at most twice, because the third occurrence would equal nums[k-2].
  4. The first two elements are always kept, so k starts at 2 (or at the array length if it is shorter).

💻 Benchmark Python3 Implementation

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) <= 2:
            return len(nums)
        k = 2                          # the first two elements are always kept
        for i in range(2, len(nums)):
            if nums[i] != nums[k - 2]:  # allow at most two occurrences
                nums[k] = nums[i]
                k += 1
        return k

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): in place.

⚠️ Interview Pitfalls & Follow-ups

  • Comparing with nums[i-2]: this uses the read stream rather than the write stream, so it fails once elements start being skipped. Compare with nums[k-2].
  • Initialising k to 0: the first two elements need no comparison, so k starts at 2 and the loop at index 2.
  • Using nums[k-1] instead of nums[k-2]: that enforces at most one occurrence, degenerating to the basic version.
  • Handling arrays of length 1 or 2: both are already valid, so the early return avoids index errors on nums[k-2].
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems

中文速览与面试要点

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

给你一个有序数组 nums,请你 原地 删除重复出现的元素,使得出现次数超过两次的元素 只出现两次 ,返回删除后数组的新长度。不要使用额外的数组空间,你必须在 原地 修改输入数组并在使用 O(1) 额外空间的条件下完成。说明:为什么返回数值是整数,但输出的答案是数组呢?请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。约束:1 ≤ nums.length ≤ 3 × 10^4;-10^4 ≤ nums[i] ≤ 10^4;nums 已按非严格递增排列。

核心要点

  • 读写双指针 + 跳跃两格比较(标准解) :k 为写指针。对每个读到的元素 x,若「已保留的元素不足 2 个」或「x 与上上个保留元素不同」,则保留它。
  • 判重条件 x != nums[k-2] 的含义 : nums[k-2] 是倒数第二个被保留的值。若 x 与它相同,说明该值已经被保留了两次,不能再保留。
  • 为什么这个条件是充分的 :数组已排序,相同的值必然连续,因此只需检查「最近两次保留」即可。
  • 推广 :把 k &lt; 2 改为 k &lt; m 、 nums[k-2] 改为 nums[k-m] ,即可推广到「每个元素最多保留 m 次」。

常见陷阱

  • 判重条件写成 x != nums[k-1] :那会退化为「每个元素只保留一次」(即 26 题)。必须与 nums[k-2] 比较。
  • 忘记 k &lt; 2 的边界 :前两个元素无需判重直接保留,否则 nums[k-2] 会越界(负下标会静默索引到末尾)。
  • 用计数器统计每个值的出现次数 :需要额外空间或额外的循环,读写指针更简洁。
  • 试图 del nums[i] :list 的删除是 O(n),整体 O(n²)。

参考实现

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        k = 0
        for x in nums:
            # 保留前两个元素,或 x 与上上个保留值不同
            if k < 2 or x != nums[k - 2]:
                nums[k] = x
                k += 1
        return k