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

◎

本节目标

利用有序性以双指针维护唯一值有效前缀。

这题继续使用双指针解题框架，但有序性让“是否保留”只需要和有效前缀的末尾比较。

查看原题

题意与约束

给定非递减数组，原地保留每个不同值一次，返回不同元素个数 k。只有 nums[0..k) 必须按原有顺序保存唯一值。

推导与不变量

暴力去重需要为每个值查询已保留集合；有序数组的重复值却连续出现。初始化时第一个元素已构成唯一前缀。对每个 read >= 1，nums[0..write) 保存已读部分的全部唯一值，且 nums[write - 1] 是最后一个唯一值。当前值不同才写入并移动 write。

原地修改

空数组返回 0。非空时返回值 k 表示唯一值有效前缀的长度，数组尾部不属于答案；算法直接覆盖 nums，额外空间为常数。

代码实现

两种语言都先处理空数组，再让读指针从下标 1 开始。比较的是当前值与有效前缀末尾，而不是与紧邻的原数组位置。

C++

C++17

#include <vector>

using namespace std;

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }

        int write = 1;
        for (int read = 1; read < static_cast<int>(nums.size()); read++) {
            if (nums[read] != nums[write - 1]) {
                nums[write] = nums[read];
                write++;
            }
        }
        return write;
    }
};

Python

Python 3

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        if not nums:
            return 0

        write = 1
        for read in range(1, len(nums)):
            if nums[read] != nums[write - 1]:
                nums[write] = nums[read]
                write += 1
        return write

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

易错点

• 忘记空数组，使初始 write = 1 越界或返回错误。
• 与 nums[read - 1] 比较后直接写入，容易让不变量不再明确；有效前缀末尾才是统一的比较对象。

模式迁移

这是一种“利用有序性压缩”的模板。若每个值最多保留两次，可让写入条件比较更早的有效前缀位置；若没有有序性，则需要额外集合或先排序。