实战：删除排序数组中的重复项 ​

这道题引入了一个重要的技巧：双指针。

双指针是数组题目中最常用的技巧之一。掌握它，你就能解决一大类"原地修改"的问题。

题目描述 ​

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

给你一个升序排列的数组 nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。

不要使用额外的空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1：

输入：nums = [1, 1, 2]
输出：2, nums = [1, 2, _]
解释：返回 2，nums 的前两个元素是 [1, 2]

示例 2：

输入：nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
输出：5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]
解释：返回 5，nums 的前五个元素是 [0, 1, 2, 3, 4]

题目分析 ​

关键点：

1. 数组已排序：相同的元素一定相邻
2. 原地修改：不能创建新数组，只能在原数组上操作
3. O(1) 空间：只能用常数个额外变量
4. 返回新长度：前 k 个元素是去重后的结果

思考一下：如果允许使用额外空间，怎么做？

创建一个新数组，遍历原数组，遇到新元素就加入。这很简单，但不符合题目要求。

原地修改怎么办？

解法：快慢双指针 ​

核心思路：用两个指针，一个用来读（遍历），一个用来写（记录结果）。

fast 指针：遍历数组，寻找新元素
slow 指针：指向下一个要写入的位置

当 nums[fast] 与前一个元素不同时，说明遇到了新元素，写入 nums[slow] 位置。

function removeDuplicates(nums) {
    if (nums.length === 0) return 0;
    
    // slow: 下一个要写入的位置
    // 第一个元素一定保留，所以从 1 开始
    let slow = 1;
    
    // fast: 遍历数组
    for (let fast = 1; fast < nums.length; fast++) {
        // 当前元素与前一个元素不同，说明是新元素
        if (nums[fast] !== nums[fast - 1]) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    
    return slow;
}

执行过程 ​

以 nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] 为例：

初始：slow = 1

fast=1: nums[1]=0, nums[0]=0, 相同 → 跳过
fast=2: nums[2]=1, nums[1]=0, 不同 → nums[1]=1, slow=2
fast=3: nums[3]=1, nums[2]=1, 相同 → 跳过
fast=4: nums[4]=1, nums[3]=1, 相同 → 跳过
fast=5: nums[5]=2, nums[4]=1, 不同 → nums[2]=2, slow=3
fast=6: nums[6]=2, nums[5]=2, 相同 → 跳过
fast=7: nums[7]=3, nums[6]=2, 不同 → nums[3]=3, slow=4
fast=8: nums[8]=3, nums[7]=3, 相同 → 跳过
fast=9: nums[9]=4, nums[8]=3, 不同 → nums[4]=4, slow=5

结果：nums = [0, 1, 2, 3, 4, ...], 返回 5

可以用图示来理解：

初始状态：
[0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
 ↑  ↑
slow fast

fast=2 时，发现新元素 1：
[0, 1, 1, 1, 1, 2, 2, 3, 3, 4]
    ↑     ↑
   slow   fast
   （写入 1 后，slow 移到 2）

fast=5 时，发现新元素 2：
[0, 1, 2, 1, 1, 2, 2, 3, 3, 4]
       ↑           ↑
      slow        fast
      （写入 2 后，slow 移到 3）

最终：
[0, 1, 2, 3, 4, 2, 2, 3, 3, 4]
                ↑
               slow=5
返回 5，表示前 5 个元素是结果

为什么比较 nums[fast] 和 nums[fast-1]？ ​

因为数组是有序的，相同元素一定相邻。如果当前元素和前一个不同，那它就是新元素。

另一种写法是比较 nums[fast] 和 nums[slow-1]（已写入的最后一个元素）：

function removeDuplicates(nums) {
    if (nums.length === 0) return 0;
    
    let slow = 1;
    
    for (let fast = 1; fast < nums.length; fast++) {
        // 与已写入的最后一个元素比较
        if (nums[fast] !== nums[slow - 1]) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    
    return slow;
}

两种写法在这道题中效果相同。但第二种写法更通用，可以扩展到"保留 k 个重复元素"的情况。

复杂度分析：

• 时间复杂度：O(n)——遍历一次数组
• 空间复杂度：O(1)——只用了两个指针变量

扩展：保留 k 个重复元素 ​

LeetCode 80 是这道题的进阶版：允许每个元素最多出现两次。

思路是一样的，只需要改一下比较条件：

function removeDuplicates(nums, k = 2) {
    if (nums.length <= k) return nums.length;
    
    let slow = k;  // 前 k 个元素直接保留
    
    for (let fast = k; fast < nums.length; fast++) {
        // 与 slow-k 位置的元素比较
        if (nums[fast] !== nums[slow - k]) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    
    return slow;
}

解释一下 nums[fast] !== nums[slow - k]：

如果当前元素和 slow - k 位置的元素不同，说明当前元素在结果数组中出现的次数还不到 k 次，可以写入。

这是一个通用模板：

• k = 1：每个元素最多出现 1 次（本题）
• k = 2：每个元素最多出现 2 次（LeetCode 80）

常见错误 ​

1. 忘记处理空数组：nums.length === 0 时直接返回 0
2. 比较对象搞错：应该比较相邻元素或与已写入的最后一个元素比较
3. 返回值理解错误：返回的是长度，不是最后一个元素的索引

相关题目 ​

• 27. 移除元素：删除所有等于某个值的元素
• 283. 移动零：把所有 0 移到数组末尾
• 80. 删除有序数组中的重复项 II：每个元素最多保留两次

这些题目的核心思路都是快慢双指针，值得练习。

本章小结 ​

这一章我们学习了快慢双指针技巧：

1. 快指针：负责遍历，寻找需要的元素
2. 慢指针：负责记录写入位置
3. 利用有序性：相同元素一定相邻，只需比较相邻元素
4. 通用模式：可以扩展到"保留 k 个重复"的场景

双指针是数组原地修改问题的核心技巧。后面你会在很多题目中见到它。

下一章，我们来看另一道双指针的经典应用：「移动零」。