双指针技巧详解：从基础到进阶（Java 实现）

三、三数之和 (3Sum) —— 排序 + 左右指针

1. 算法思路

• 排序：使数组有序，方便使用双指针并进行去重。
• 枚举：固定第一个数 a，在剩下的区间里通过双指针寻找 b 和 c，使得 a + b + c = 0。

2. Java 代码实现

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        // 1. 先排序
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // 如果当前数大于 0，由于数组有序，后续三个数之和一定大于 0
            if (nums[i] > 0) break;
            // 2. 对第一个数 a 去重：如果当前数和前一个数相同，跳过
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 3. 对第二个数 b 去重
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    // 4. 对第三个数 c 去重
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++; // 和太小，左指针右移增加数值
                } else {
                    right--; // 和太大，右指针左移减小数值
                }
            }
        }
        return ans;
    }
}

四、接雨水 (Trapping Rain Water) —— 双指针巅峰

1. 算法思路

• 单点逻辑：位置 i 能接的水 = min(leftMax, rightMax) - height[i]。
• 双指针优化：我们不需要预处理所有高度，只需要用两个指针从两侧向中间靠拢。

2. Java 代码实现

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        // 记录左边和右边遇到的最高高度
        int res = 0;
        while (left < right) {
            // 更新左右两侧目前的最高墙
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            // 如果左边的墙比右边的墙矮
            // 意味着：对于 left 这个点，接多少水取决于左侧的 leftMax（因为右侧一定有比它更高的墙）
            if (leftMax < rightMax) {
                res += (leftMax - height[left]);
                left++;
            } else {
                // 反之，right 这个点接多少水取决于右侧的 rightMax
                res += (rightMax - height[right]);
                right--;
            }
        }
        return res;
    }
}

总结：双指针解题的思考模版

1. 场景识别：

   • 同向指针（快慢指针）：常用于处理'原地修改'或'寻找循环/中点'。
   • 相向指针（对撞指针）：常用于处理'有序数组寻找两数/多数之和'或'区间极值（盛水/接水）'。

2. 核心三要素：

   • 指针初始化：是 (0, length-1) 还是 (0, 0)？
   • 移动条件：什么情况下左移？什么情况下右移？（通常依据单调性判断）。
   • 收缩条件：如何有效跳过重复解（去重）以保证效率？

通过以上四道题的练习，你应该能感受到双指针在降低时间复杂度方面的巨大威力。