双指针：对撞指针与快慢指针

双指针是什么

双指针（Two Pointers）是一种利用数组的有序性或结构特征，用两个游标代替暴力双层循环的技巧，把 O(n²) 降为 O(n)。

根据指针的移动方向：

• 对撞指针（Opposite Direction）：left 从左、right 从右，向中间靠拢
• 快慢指针（Same Direction）：两个指针同向移动，快指针跑得更快

对撞指针

两端向中间夹逼，核心在于每次移动肯定没用的那一端。

两数之和 II（LeetCode 167）

有序数组，找两个数使其和为 target：

int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) return new int[]{left + 1, right + 1};
        if (sum < target) left++;   // 和太小，左指针右移
        else right--;               // 和太大，右指针左移
    }
    return new int[]{-1, -1};
}

为什么可以移动一端？ 数组有序。当 sum < target 时，right 已经是当前最大，再配什么都不够，所以左移 left；反之同理。

{
  "type": "array-pointer",
  "title": "两数之和 II — target=9，数组=[2,3,4,6,8,11]",
  "steps": [
    {
      "note": "初始：left=0, right=5，sum=2+11=13 > 9，移动 right",
      "array": [2, 3, 4, 6, 8, 11],
      "pointers": { "L": 0, "R": 5 },
      "highlight": [0, 5]
    },
    {
      "note": "sum=2+8=10 > 9，继续移动 right",
      "array": [2, 3, 4, 6, 8, 11],
      "pointers": { "L": 0, "R": 4 },
      "highlight": [0, 4]
    },
    {
      "note": "sum=2+6=8 < 9，移动 left",
      "array": [2, 3, 4, 6, 8, 11],
      "pointers": { "L": 0, "R": 3 },
      "highlight": [0, 3]
    },
    {
      "note": "sum=3+6=9 == target，找到答案！返回 [2,4]（1-indexed）",
      "array": [2, 3, 4, 6, 8, 11],
      "pointers": { "L": 1, "R": 3 },
      "highlight": [1, 3],
      "matched": [1, 3]
    }
  ]
}

反转字符串（LeetCode 344）

经典对撞：左右互换，向中心收缩：

void reverseString(char[] s) {
    int left = 0, right = s.length - 1;
    while (left < right) {
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

三数之和（LeetCode 15）

固定第一个数，剩余两个用对撞指针：

List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;  // 去重
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++; right--;
            } else if (sum < 0) left++;
            else right--;
        }
    }
    return res;
}

快慢指针

同向移动，通常 fast 比 slow 多走几步，解决原地操作问题。

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

slow 指向下一个要写入的位置，fast 探索新元素：

int removeDuplicates(int[] nums) {
    int slow = 0;
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];  // 写入新元素
        }
    }
    return slow + 1;
}

{
  "type": "array-pointer",
  "title": "删除有序数组重复项 [1,1,2,3,3,4]",
  "steps": [
    {
      "note": "slow=0, fast=1，nums[1]==nums[0]，fast 跳过",
      "array": [1, 1, 2, 3, 3, 4],
      "pointers": { "slow": 0, "fast": 1 },
      "highlight": [0, 1]
    },
    {
      "note": "fast=2，nums[2]=2 != nums[0]=1，slow++，写入 nums[1]=2",
      "array": [1, 2, 2, 3, 3, 4],
      "pointers": { "slow": 1, "fast": 2 },
      "highlight": [1, 2]
    },
    {
      "note": "fast=3，nums[3]=3 != nums[1]=2，slow++，写入 nums[2]=3",
      "array": [1, 2, 3, 3, 3, 4],
      "pointers": { "slow": 2, "fast": 3 },
      "highlight": [2, 3]
    },
    {
      "note": "fast=4，nums[4]=3 == nums[2]=3，跳过",
      "array": [1, 2, 3, 3, 3, 4],
      "pointers": { "slow": 2, "fast": 4 },
      "highlight": [2, 4]
    },
    {
      "note": "fast=5，nums[5]=4 != nums[2]=3，slow++，写入 nums[3]=4。结束，返回 slow+1=4",
      "array": [1, 2, 3, 4, 3, 4],
      "pointers": { "slow": 3, "fast": 5 },
      "highlight": [3, 5],
      "matched": [0, 1, 2, 3]
    }
  ]
}

移动零（LeetCode 283）

先把非零元素搬到前面，再把 slow 之后填零：

void moveZeroes(int[] nums) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            nums[slow++] = nums[fast];
        }
    }
    while (slow < nums.length) {
        nums[slow++] = 0;
    }
}

盛最多水的容器（LeetCode 11）

height[left] 和 height[right] 决定面积，每次移动更矮的那侧：移动矮侧才可能让面积增大；移动高侧面积只会减小（宽度已在缩小）。

int maxArea(int[] height) {
    int left = 0, right = height.length - 1, res = 0;
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        res = Math.max(res, area);
        if (height[left] < height[right]) left++;
        else right--;
    }
    return res;
}

选择对撞指针还是快慢指针？