双指针算法详解

双指针是用两个指针在数组/链表上遍历，通过调整指针位置来解决问题的技巧。

一、什么是双指针

双指针就像两个人从两端向中间走，或者一前一后向前走。

两个指针的作用：
- 一个指针遍历已处理的数据
- 另一个指针寻找目标位置

好处：避免嵌套循环，将 O(n²) 降为 O(n)

常见模式：

模式	说明	适用场景
左右指针	left 从左开始，right 从右开始	排序数组、容器问题
快慢指针	fast 走得快，slow 走得慢	链表、原地操作

二、实战例题

2.1 盛最多水的容器

题目： 在数组中找两条线，使它们与 x 轴构成的容器能盛最多的水

输入：[1,8,6,2,5,4,8,3,7]
输出：49

核心思路： 左右指针从两端开始，每次移动较短的指针

public class ContainerWithMostWater {

  public static int maxArea(int[] height) {
    if (height == null || height.length == 0) return 0;

    int sum = 0;
    int left = 0;
    int right = height.length - 1;

    while (left < right) {
      // 计算当前区域的面积
      int currentArea = (right - left) * Math.min(height[left], height[right]);
      sum = Math.max(sum, currentArea);

      // 移动较短的指针，因为容积受限于较短的边
      if (height[left] < height[right]) {
        left++;
      } else {
        right--;
      }
    }

    return sum;
  }

  public static void main(String[] args) {
    int[] arr = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    // 输出: 49
  }
}

理解要点：

• 两端向中间收缩，每次移动较短的边
• 移动较短的边才有可能让容积变大
• 移动较长的边只会让容积更小或不变

2.2 三数之和

题目： 在数组中找到所有不重复的三元组，和为 0

输入：[-1, 0, 1, 2, -1, -4]
输出：[[-1, -1, 2], [-1, 0, 1]]

核心思路： 固定一个指针，双指针找另外两个数

import java.util.*;

public class ThreeSum {

  public static List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);  // 先排序，方便跳过重复和双指针查找
    HashMap<Integer, Integer> hashMap = new HashMap<>();

    // 存储每个数字及其下标，方便查找第三个数
    for (int i = 0; i < nums.length; i++) {
      hashMap.put(nums[i], i);
    }

    Set<List<Integer>> lists = new HashSet<>();

    // left 指针只遍历到倒数第三个，留两个位置给另外两个数
    for (int left = 0; left < nums.length - 2; left++) {
      // 跳过重复的 left
      if (left > 0 && nums[left] == nums[left - 1]) {
        continue;
      }

      for (int right = left + 1; right < nums.length - 1; right++) {
        // 跳过重复的 right
        if (right > left + 1 && nums[right] == nums[right - 1]) {
          continue;
        }

        // 寻找第三个数：0 - (left + right)
        int target = -(nums[left] + nums[right]);

        if (hashMap.containsKey(target)) {
          int thirdIndex = hashMap.get(target);
          // 确保第三个数的下标在 right 后面
          if (thirdIndex > right) {
            List<Integer> list = new ArrayList<>();
            list.add(nums[left]);
            list.add(nums[right]);
            list.add(target);
            Collections.sort(list);
            lists.add(list);
          }
        }
      }
    }

    return new ArrayList<>(lists);
  }
}

理解要点：

• 先排序，再处理，可以避免重复三元组
• 固定一个数，双指针找另外两个数
• 通过哈希表快速查找第三个数

2.3 接雨水

题目： 计算下雨后能接多少雨水

输入：[0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

核心思路： 左右指针同时遍历，记录左右两边的最大高度

public class TrappingRainWater {

  public static int trap(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int ans = 0;
    int leftMax = 0, rightMax = 0;

    while (left < right) {
      // 更新两边的最大高度
      leftMax = Math.max(leftMax, height[left]);
      rightMax = Math.max(rightMax, height[right]);

      // 哪边矮，就计算哪边能接的雨水
      if (height[left] < height[right]) {
        ans += leftMax - height[left];
        left++;
      } else {
        ans += rightMax - height[right];
        right--;
      }
    }

    return ans;
  }

  public static void main(String[] args) {
    int[] arr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    // 输出: 6
  }
}

理解要点：

• 当前位置能接的雨水 = min(左边最高, 右边最高) - 当前高度
• 哪边最高高度小，就计算哪边
• 不需要知道所有位置的高度，只需要当前能确定的一边

三、总结

题目	双指针类型	核心思路
盛最多水	左右指针	从两端开始，移动较短的指针
三数之和	左右指针 + 哈希	固定一个，双指针找另外两个
接雨水	左右指针	哪边矮就算哪边的雨水

双指针使用场景：

• 数组已排序，需要查找目标值
• 需要在一次遍历中完成查找
• 原地操作，避免额外空间