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

Categories:

题目描述
思路分析
1. 解法一：双指针（推荐）
2. 解法二：通用化 k 次重复
相似题目

题目描述

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

思路分析

解法一：双指针（推荐）

核心思路：

使用快慢双指针，slow 指向下一个写入位置，fast 遍历数组。

由于数组有序，每个元素最多保留 2 次，只需判断当前元素是否与 nums[slow - 2] 相同。

若 nums[fast] != nums[slow - 2]，说明当前元素还没有超过 2 次，可以写入；否则跳过。

前两个元素无需判断，直接保留（slow 初始值为 2）。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组的长度，fast 指针遍历一次数组。

空间复杂度：O(1)，原地修改，不使用额外空间。

class Solution {
    public int removeDuplicates(int[] nums) {
        // slow 指向下一个写入位置，前两个元素直接保留
        int slow = 2;
        for (int fast = 2; fast < nums.length; fast++) {
            // 当前元素与写入位置前两位不同，说明未超过2次，可写入
            if (nums[fast] != nums[slow - 2]) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

func removeDuplicates(nums []int) int {
    // slow 指向下一个写入位置，前两个元素直接保留
    slow := 2
    for fast := 2; fast < len(nums); fast++ {
        // 当前元素与写入位置前两位不同，说明未超过2次，可写入
        if nums[fast] != nums[slow-2] {
            nums[slow] = nums[fast]
            slow++
        }
    }
    return slow
}

解法二：通用化 k 次重复

核心思路：

将解法一推广到允许最多保留 k 次重复的通用场景。

条件改为 nums[fast] != nums[slow - k]，当 k=2 时即退化为解法一。

同样地，前 k 个元素直接保留（slow 初始值为 k）。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组的长度，fast 指针遍历一次数组。

空间复杂度：O(1)，原地修改，不使用额外空间。

class Solution {
    public int removeDuplicates(int[] nums) {
        // k=2，允许每个元素最多出现2次
        return removeDuplicatesAtMostK(nums, 2);
    }

    private int removeDuplicatesAtMostK(int[] nums, int k) {
        // slow 初始为 k，前 k 个元素直接保留
        int slow = k;
        for (int fast = k; fast < nums.length; fast++) {
            // 当前元素与写入位置前 k 位不同，可以写入
            if (nums[fast] != nums[slow - k]) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

func removeDuplicates(nums []int) int {
    // k=2，允许每个元素最多出现2次
    return removeDuplicatesAtMostK(nums, 2)
}

func removeDuplicatesAtMostK(nums []int, k int) int {
    // slow 初始为 k，前 k 个元素直接保留
    slow := k
    for fast := k; fast < len(nums); fast++ {
        // 当前元素与写入位置前 k 位不同，可以写入
        if nums[fast] != nums[slow-k] {
            nums[slow] = nums[fast]
            slow++
        }
    }
    return slow
}

相似题目

题目	难度	考察点
26. 删除有序数组中的重复项	简单	双指针、数组
27. 移除元素	简单	双指针、数组
283. 移动零	简单	双指针、数组
75. 颜色分类	中等	双指针、数组
11. 盛最多水的容器	中等	双指针
189. 轮转数组	中等	数组原地操作

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/69245405