如何原地去除有序数组中的重复元素？

简化版

用快慢双指针：慢指针 slow 指向「已去重部分的最后一个位置」，快指针 fast 向前扫。每当 fast 遇到一个和 slow 处不同的新值，就把 slow 往前挪一格、把新值写进去。因为数组有序，重复元素必然相邻，一趟扫描 O(n) 就能原地去重，不用额外空间。

详细版

前提：数组已排序，所以相同的元素都挨在一起。目标：原地（不开新数组）去重，返回去重后的长度。

int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int slow = 0;                       // [0..slow] 是已去重的部分
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) { // 遇到新值
            slow++;
            nums[slow] = nums[fast];    // 写到去重区的下一个位置
        }
        // 相等则跳过，fast 继续前进
    }
    return slow + 1;                    // 去重后长度
}

slow 之前（含 slow）是不重复的结果区。
fast 负责探路，找到新值就搬到结果区尾部。
时间 O(n)、空间 O(1)。

「原地」不代表数组变短了——数组长度不可变，我们是把去重结果压到前 slow+1 个位置，返回这个有效长度，后面的元素不管。

完整版教学

一、为什么「有序」是关键前提

如果数组无序，重复元素可能散落各处，想去重要么排序、要么用哈希集合（O(n) 额外空间）。而有序数组里，所有相等的元素必然连续排在一起，于是只要「和前一个不同就是新值」，一次线性扫描即可判断，不需要任何额外数据结构。这就是为什么这题限定「有序」——它让 O(1) 空间成为可能。

二、快慢指针的分工

这是双指针里的「快慢指针」模式：

慢指针 slow：维护结果区的边界，nums[0..slow] 保证无重复。
快指针 fast：遍历原数组，逐个检查。

两者速度不同：fast 每步都走，slow 只在「发现新值」时才走一步。最终 slow 走过的距离就是去重后的元素个数减一。

三、逐步走一遍

nums = [1, 1, 2, 2, 3]
初始 slow=0 (值1)
fast=1: nums[1]=1 == nums[0]=1，跳过
fast=2: nums[2]=2 != 1，slow→1，nums[1]=2  →  [1,2,2,2,3]
fast=3: nums[3]=2 == nums[1]=2，跳过
fast=4: nums[4]=3 != 2，slow→2，nums[2]=3  →  [1,2,3,2,3]
返回 slow+1 = 3，前三个 [1,2,3] 即结果

后面的 [2,3] 是残留的旧数据，调用方只用前 3 个。

四、变体：允许每个元素最多保留 K 个

经典进阶是「最多保留 2 个重复」。技巧是把比较对象从 nums[slow] 改成 nums[slow - k + 1]（往前数 k 个）：

// 每个值最多保留 2 个
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
    if (slow < 2 || nums[fast] != nums[slow - 2]) {
        nums[slow++] = nums[fast];
    }
}
return slow;

思路一致：只要当前值和「结果区往前第 k 个」不同，就可以保留。

五、和「移除指定元素」是一类题

这类「原地修改数组、用快慢指针把要保留的元素前移」的题是一个套路：慢指针指向下一个该写入的位置，快指针筛选。移除某个值、去重、移动零到末尾，本质都是它。掌握「slow 写、fast 读筛选」这个框架就能通吃。

题型	保留条件	`slow` 含义
有序数组去重	当前值不同于结果区最后一个值	已去重结果的末尾下标
每个值最多保留 2 个	当前值不同于结果区倒数第 2 个值	下一个可写入位置
移除指定元素	当前值不等于目标值	下一个可写入位置
移动零	当前值非 0	下一个非零元素写入位置

具体例子：[0,0,1,1,1,2,2,3] 去重时，slow 最终停在下标 3，前 4 个元素变为 [0,1,2,3]。如果变体要求每个元素最多保留 2 个，则结果前缀是 [0,0,1,1,2,2,3]，判断条件要从“和最后一个不同”改成“和倒数第 k 个不同”。

原地去重返回的是“有效长度”，不是让底层数组物理缩短。面试代码通常只保证前 len 个元素正确。

六、常见误区与追问

误区：去重后必须清空数组后面的旧值。 题目一般只要求返回有效长度，后面的残留值不参与结果。
误区：无序数组也能用同一套相邻比较。 快慢指针去重依赖有序性，因为重复元素必须相邻；无序数组通常要哈希或先排序。
误区：slow 一定从 1 开始。 写法可以不同，关键是不变量清楚；有的写法让 slow 表示结果区末尾，有的表示下一个写入位置。
追问：为什么时间复杂度是 O(n)？ fast 从头到尾扫描一次，每个元素最多被读一次、必要时写一次。
追问：为什么空间复杂度是 O(1)？ 只使用常数个指针变量，结果复用原数组前缀。
追问：允许最多保留 k 个怎么写？ 用 slow < k || nums[fast] != nums[slow-k] 判断，保留结果区中不超过 k 个相同值。

七、加强记忆

有序数组原地去重用快慢双指针：slow 守着去重区边界、fast 探路，fast 遇到和 slow 不同的新值就 slow++ 并写入，一趟 O(n)、空间 O(1)。前提是有序（重复元素相邻）。同一套「slow 写、fast 读筛选」框架能解移除元素、移动零、保留 K 个重复等一类题。

简化版

详细版