双指针常见的三大类用法：

其实双指针可以归为 三类策略，分别是：

1. 对撞指针（Two Pointers from Both Ends）

• 两个指针从数组/字符串两端向中间靠拢
• 应用场景： 有序数组求和、回文判断、左右逼近解空间

---

2. 滑动窗口（Sliding Window）

• 两个指针从同一端出发，维护一个「窗口」
• 一般是右指针拓展窗口，左指针收缩窗口
• 应用场景： 子串、子数组问题，最小长度/最大长度

---

3. 快慢指针（Fast and Slow Pointer）

• 两个指针速度不同（常用于链表）
• 快指针每次移动两步，慢指针一步
• 应用场景：
  • 判断链表有无环
  • 找环的入口
  • 找中点、删除倒数第 k 个节点

283.移动零

给定一个数组 nums，将所有 0 移动到数组末尾，同时保持非零元素的相对顺序不变。原地操作，不使用额外空间。

class Solution {
    public void moveZeroes(int[] nums) {
        int zeroP = 0;
        int p = 0;

        for (; p < nums.length; p++) {
            if (nums[p]!=0){
                int temp = nums[p];
                nums[p] = nums[zeroP];
                nums[zeroP] = temp;
                zeroP++;
            }
        }
    }
    
}

使用两个指针：

• p：快指针，用于遍历数组。
• zeroP：慢指针，用于指向下一个要放置非零元素的位置（也就是“遇到的第一个 0 的位置”）。

遍历逻辑：

• 快指针 p 每一步都在向前走。
• 当 nums[p] != 0：
  • 将当前 nums[p] 与 nums[zeroP] 交换。
  • 然后 zeroP++，意味着下一个非零元素应该放在下一个 0 的位置。

11.盛最多水的容器

11. 盛最多水的容器

给定一个整数数组 height，每个元素代表坐标轴上一条竖线的高度。我们选择其中任意两条线，与 x 轴构成一个容器，其容量由两线之间的距离与较短的线决定。你的任务是找出这个容器能容纳的最多水量。

🎯 解题关键点

1. 两线之间距离越远越好
2. 高度以较短的那一条为准
3. 目标是使面积 = (距离) × (较小高度) 最大

这个题目的关键是：寻找最优组合，遍历所有组合太慢（O(n²)），所以我们引入一种更高效的策略 —— 双指针法。

🧠 双指针思想解析

使用两个指针 left 和 right 分别指向数组两端，表示当前考虑的两条边。初始状态下，形成的是最宽的容器。

核心策略为：每次移动高度较小的一端。
其原因在于：

• 容器容量受限于两边中的较小高度；
• 保留较短边、移动较长边无法提升高度，且宽度减小，容量只会减少；
• 移动较短边，可能获得更大的高度，从而在宽度减小时提升容量。

public static int maxArea(int[] height) {
    int left = 0;
    int right = height.length-1;

    int result = 0;
    while (!(left==right)){
        int tHeight=Math.min(height[left],height[right]);
        int size = tHeight*(right-left);
        if (size>result){
            result=size;
        }
        if (height[left]==tHeight){
            left++;
        }else{
            right--;
        }
    }

    return result;
}

15.三数之和

两种思路：

1.双指针（三指针）：

固定一个first，另外两个同向移动，遇到重复的连续跳过。

public static List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();

    //先排序，使得双向指针移动有逻辑、并且可以去重
    Arrays.sort(nums);

    //固定一个first，另外两个同向移动，遇到重复的连续跳过。当first>0就找不到了。
    for (int first = 0; first < nums.length - 2; first++) {
        if (first > 0 && nums[first] == nums[first - 1]) continue;
        if (nums[first] > 0) break;

        int left = first + 1;
        int right = nums.length - 1;

        while (left < right) {
            int sum = nums[first] + nums[left] + nums[right];
            if (sum == 0) {
                result.add(Arrays.asList(nums[first], nums[left], nums[right]));
                left++;
                right--;
                //去重
                while (left < right && nums[left] == nums[left - 1]) left++;
                while (left < right && nums[right] == nums[right + 1]) right--;
            } else if (sum < 0) {
                //sum<0说明要往大走，即left右移
                left++;
                //去重
                while (left < right && nums[left] == nums[left - 1]) left++;
            } else {
                //对称逻辑
                right--;
                //去重
                while (left < right && nums[right] == nums[right + 1]) right--;
            }
        }
    }
    return result;
}

2.固定一个，“两数之和”

用hash表。

public static List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums); // 排序是为了后续去重方便

    for (int i = 0; i < nums.length - 2; i++) {
        // 跳过重复 a
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int target = -nums[i];
        Set<Integer> seen = new HashSet<>();
        for (int j = i + 1; j < nums.length; j++) {
            int complement = target - nums[j];
            if (seen.contains(complement)) {
                res.add(Arrays.asList(nums[i], complement, nums[j]));

                // 跳过重复 b
                while (j + 1 < nums.length && nums[j] == nums[j + 1]) j++;
            }
            seen.add(nums[j]);
        }
    }

    return res;
}

另外，「四数之和」「k数之和」等问题的通用解法就是通过递归地将问题转化为“两数之和”。

42.接雨水

public static int trap(int[] height) {
    //时间复杂度为 O (n)，空间复杂度为 O (1)。
    int ans=0;
    int left = 0;
    int right = height.length-1;
    int preMax = 0;
    int sufMax = 0;

    while (left<=right){
        //更新前缀最大值和后缀最大值
        preMax = Math.max(height[left],preMax);
        sufMax = Math.max(height[right],sufMax);

        //当前位置接水高度取决于左右边界中较小的值
        if (preMax<sufMax){
            //如果当前前缀最大值小于后缀最大值，那么前缀最大值就是要求的“较小的值”，因为后缀最大值不能更小了。
            ans+=preMax-height[left];
            left++;
        }else {
            //同理对称，此处包含相等的逻辑，相等时谁减底座都一样。
            ans+=sufMax-height[right];
            right--;
        }
    }

    return ans;
}