双指针技巧：删除有序数组中的重复项

一、引言

双指针是一种常见且高效的算法技巧，特别适用于数组和链表操作。在处理有序数组的去重、查找、移动等问题时，双指针技巧能够在不使用额外空间的情况下高效完成任务。本文将深入探讨双指针中的快慢指针技巧，并以"删除有序数组中的重复项"为例，详细分析其实现原理和应用场景。

二、双指针技巧概述

1. 什么是双指针

双指针技巧是指在遍历数据结构时使用两个指针，通过指针的移动和交互来解决问题。这种技巧通常能将时间复杂度从O(n²)降低到O(n)，同时保持空间复杂度为O(1)。

2. 常见的双指针类型

快慢指针：两个指针以不同的速度在数组或链表上移动
- 一个指针（慢指针）通常负责记录结果
- 另一个指针（快指针）负责探索和遍历
左右指针：两个指针分别从数组的两端向中间移动
- 常用于有序数组的二分查找、对撞指针问题等
滑动窗口：两个指针维护一个窗口，根据条件扩大或缩小窗口
- 常用于子数组和子串问题

三、快慢指针详解

1. 基本原理

快慢指针是双指针的一种特殊形式，其特点是：

慢指针：通常用于跟踪结果位置或满足特定条件的元素
快指针：用于遍历整个数组或链表
两个指针通常从同一位置开始，但以不同的"速度"前进

2. 适用场景

快慢指针特别适用于以下场景：

原地删除数组中的特定元素
原地移动数组元素（如移动零到末尾）
检测链表中是否存在环
查找链表的中间节点
查找链表倒数第k个节点

3. 实现模式

快慢指针的典型实现模式：

初始化慢指针 slow = 0
初始化快指针 fast = 0 或 fast = 1（取决于具体问题）

遍历数组/链表：
    根据条件移动快指针
    根据条件移动慢指针并修改元素
    
返回慢指针位置或相关结果

四、案例分析：删除有序数组中的重复项

1. 问题描述

给定一个 非严格递增排列 的数组 nums，要求：

原地删除重复出现的元素，使每个元素只出现一次
保持元素的相对顺序不变
返回删除后数组的新长度k
确保数组的前k个元素包含所有唯一元素

2. 解题思路

由于数组已经有序，相同元素必定相邻。我们可以使用快慢指针：

慢指针(slow)：指向当前已处理好的不重复元素的最后位置
快指针(fast)：遍历整个数组，寻找新的不重复元素

算法步骤：

初始化慢指针 slow = 0
快指针 fast 从位置1开始遍历数组
比较 nums[fast] 和 nums[slow]：
- 如果不相等，说明找到了新的不重复元素，将 slow 前进一步，并将 nums[fast] 复制到 nums[slow] 位置
- 如果相等，只移动 fast，忽略重复元素
返回 slow + 1（不重复元素的个数）

3. 算法图解

以数组 [1,1,2,2,3,4,4,5] 为例，演示快慢指针的工作过程：

初始状态：

nums = [1, 1, 2, 2, 3, 4, 4, 5]
        ↑  ↑
      slow fast

第1步：nums[fast] == nums[slow]，只移动fast

nums = [1, 1, 2, 2, 3, 4, 4, 5]
        ↑     ↑
      slow   fast

第2步：nums[fast] != nums[slow]，将2复制到slow+1位置，然后slow前进

nums = [1, 2, 2, 2, 3, 4, 4, 5]
           ↑     ↑
         slow   fast

第3步：nums[fast] == nums[slow]，只移动fast

nums = [1, 2, 2, 2, 3, 4, 4, 5]
           ↑        ↑
         slow      fast

第4步：nums[fast] != nums[slow]，将3复制到slow+1位置，然后slow前进

nums = [1, 2, 3, 2, 3, 4, 4, 5]
              ↑     ↑
            slow   fast

最终结果：

nums = [1, 2, 3, 4, 5, 4, 4, 5]
                    ↑
                  slow

返回 slow + 1 = 5，表示有5个不重复元素。

4. 代码实现

public int removeDuplicates(int[] nums) {
    // 处理边界情况
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    int slow = 0; // 慢指针，指向当前不重复元素的位置
    
    // 快指针从位置1开始遍历
    for (int fast = 1; fast < nums.length; fast++) {
        // 如果当前元素与慢指针指向的元素不同
        if (nums[fast] != nums[slow]) {
            // 将不重复的元素移动到slow+1的位置
            nums[++slow] = nums[fast];
        }
        // 如果相同，fast继续前进，slow不动
    }
    
    // slow+1 就是不重复元素的个数
    return slow + 1;
}

5. 复杂度分析

时间复杂度：==O(n)==，其中n是数组的长度。我们只需要遍历一次数组。
空间复杂度：==O(1)==，只使用了常数级别的额外空间。

五、快慢指针的其他应用

1. 移除元素

问题：给定数组和一个值val，原地移除所有等于val的元素并返回新长度。

public int removeElement(int[] nums, int val) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}

2. 移动零

问题：将数组中的所有0移动到末尾，同时保持非零元素的相对顺序。

public void moveZeroes(int[] nums) {
    int slow = 0;
    // 先将非零元素都移到前面
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            nums[slow++] = nums[fast];
        }
    }
    // 将剩余位置填充为0
    while (slow < nums.length) {
        nums[slow++] = 0;
    }
}

3. 检测链表中的环

问题：判断链表中是否存在环。

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    
    ListNode slow = head;
    ListNode fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;       // 慢指针每次移动一步
        fast = fast.next.next;  // 快指针每次移动两步
        
        if (slow == fast) {     // 如果两指针相遇，说明有环
            return true;
        }
    }
    
    return false;  // 如果快指针到达链表尾部，说明无环
}

六、总结

关键知识点

快慢指针是双指针技巧的一种，通过使用两个以不同"速度"移动的指针来解决问题。在删除有序数组中重复项的问题中，慢指针用于跟踪不重复元素的位置，快指针用于遍历数组寻找新的不重复元素。这种方法能够在O(n)时间内完成去重，且只需要O(1)的额外空间。

深入解析

快慢指针的工作原理：
- 慢指针维护不重复元素的边界
- 快指针探索整个数组
- 只有当发现新的不重复元素时，慢指针才会前进
为什么这种方法适用于有序数组：
- 有序数组中相同元素一定相邻
- 通过比较相邻元素可以检测重复
- 不需要使用额外数据结构记录已见过的元素
进阶问题：
- 如何处理允许重复元素出现k次的情况？
  答：使用计数器或修改比较条件，只有当元素出现超过k次时才跳过
- 如果数组无序，如何处理？
  答：可以先排序，或者使用哈希表记录已见过的元素，但空间复杂度会变为O(n)
- 如何在链表中应用类似技巧？
  答：链表中应用类似，但需要注意指针操作和内存管理

双指针技巧-删除有序数组中的重复项