双指针：两个下标抵掉一层循环

这一课你将能做到

1. 说出双指针两种形态（对撞型、快慢型）分别适合什么题
2. 独立写出「盛最多水的容器」和「三数之和」的完整代码并处理去重
3. 解释为什么排序 + 双指针能把 O(n²) / O(n³) 的暴力枚举压到 O(n²) 甚至 O(n)

为什么要学

上一课的哈希是「用空间换时间」，双指针则常常不需要额外空间就能降复杂度：两个下标在一次遍历里互相配合，该让左的让左、该让右的让右，把「枚举所有两两组合」的双重循环压缩成一次扫描。

这类题在面试中出现频率极高，而且有个温柔的特点：套路固定、代码短，非常适合作为中等题的突破口。判断信号通常是——数组有序（或可以先排序）、要在两端之间做选择、或者要原地操作数组。

先建立图像

两种基本形态：

对撞型（左右指针）            快慢型（同向指针）
  left →              ← right   slow →        fast →→
[1, 2, 5, 7, 9, 12]            [0, 1, 0, 3, 12]
  每次根据条件移动其中一端        fast 探路，slow 负责写结果

对撞型的移动逻辑是本课核心。以「两数之和（有序版）」为例：如果 nums[left] + nums[right] 比 target 小，说明和太小，只能把 left 右移让左边变大；此时若把 right 左移，和只会更小，毫无帮助。和太大则反过来 right--。每一步都在排除不可能，而不是瞎试。

跟着做

步骤 1：LeetCode 125「验证回文串」（简单，热身）

判断字符串忽略大小写、只看字母和数字时是否正读反读相同，如 "A man, a plan, a canal: Panama" 是回文。

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            // 跳过非字母数字
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

要点：左右指针各自跳过无效字符后比较。时间 O(n)，空间 O(1)。这是最朴素的对撞模板。

步骤 2：LeetCode 11「盛最多水的容器」（中等）

数组 height 的每个值是一条竖线的高度，任选两条线与 x 轴围成容器，求最大盛水量。面积公式：min(height[left], height[right]) * (right - left)。

暴力是 O(n²) 枚举每一对。双指针从最宽的两端开始，关键问题是：该移动哪一边？ 宽度每一步都在变小，想让面积有机会变大，只能指望短板变高。所以——移动较短的那一边；移动长板，短板不变、宽度还更小，面积绝不可能更大。

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int best = 0;
        while (left < right) {
            int h = Math.min(height[left], height[right]);
            int width = right - left;
            best = Math.max(best, h * width);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return best;
    }
}