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

这一课你将能做到

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;
    }
}

逐点讲：每次移动短板都在安全地排除一批「绝不可能更优」的组合，因此不会漏掉答案。时间 O(n)，空间 O(1)。面试时能把「为什么移动短边」讲清楚，比写出代码更重要。

步骤 3：LeetCode 15「三数之和」（中等）

给定数组 nums，找出所有和为 0 且不重复的三元组。

思路拆解：三数之和 = 固定一个数 nums[i]，剩下两数在有序数组里做「对撞双指针」。所以先排序（O(n log n)），再用一层循环 + 双指针（O(n²)），总体 O(n²)，比暴力 O(n³) 快一个量级。

去重有两处：外层固定的数不能和上一个相同；找到一组答案后，左右指针也要跳过相邻的重复值。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) {
                break; // 最小的数都大于 0，三数之和不可能为 0
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue; // 外层去重
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], 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) {
                    left++;   // 和太小
                } else {
                    right--;  // 和太大
                }
            }
        }
        return result;
    }
}

逐点讲：排序后双指针的移动方向完全由 sum 与 0 的大小关系决定，和有序两数之和一模一样。时间 O(n²)，空间 O(log n)（排序所需，不计结果存储）。

讲清楚要点

1. 对撞指针的前提是「移动方向可判定」：通常要先排序，或像盛水容器那样能根据问题性质判断该移动哪边。
2. 每移动一次都在排除不可能解：这是双指针正确性的来源，面试要能说出「为什么不会漏掉」。
3. 三数之和的本质是「一静 + 两动」：外层枚举一个数，内层对撞找另外两个；四数之和（LeetCode 18）就是两层固定 + 双指针。
4. 去重发生在两个位置：枚举的固定值、找到解之后的指针两侧，写漏任何一处都会输出重复三元组。
5. 快慢型指针的代表是链表题和原地数组题：如移动零、删除有序数组重复项，下一课的链表环检测也是它。

你可能会懵的地方

• 盛水容器为什么移动长板一定没机会？ 当前短板决定高度。移动长板后宽度减小，而短板没变，新面积 = 短板 × 更小宽度，必然不大于当前面积，所以这些组合可以安全排除。

• 三数之和里 while 去重为什么和 if 不一样？ 重复值可能连续出现很多个（如 [-2,-2,-2,...]），必须用 while 一路跳完；if 只跳一个，剩下的重复值还会生成重复答案。

• 为什么外层去重写 nums[i] == nums[i-1]，不能看 nums[i+1] 吗？ 要跳过的是「和上一次枚举相同」的值。看后一个会把合法的首组解也跳掉，例如 [-1,-1,2]。

• 双指针和二分查找是什么关系？ 思想同源：都在「排除一半 / 一批不可能」。二分是每次排除一半区间，双指针是每步从两端收缩。二分可以看作双指针的特殊严格形态。

• Arrays.asList(...) 生成的列表能修改吗？ 不能增删，它是定长视图。本题只是放进结果不再改，所以没问题；需要可变列表就用 new ArrayList<>(Arrays.asList(...))。

错法对照

错法	问题	正解
三数之和不排序直接双指针	无法判断指针移动方向	先 Arrays.sort
盛水容器移动较高的一边	排除不掉任何组合，可能漏最优	永远移动短边
找到一组解后只移动一个指针	要么死循环要么漏去重	left++ 和 right-- 同时做
用 if 跳过连续重复值	重复值超过两个时仍重复	用 while 跳干净
循环条件写成 left <= right	left==right 时同一元素被用两次	三数之和用 left < right

卡点急救

1. 输出里有重复三元组：查两个位置——外层 i 是否跳过了 nums[i]==nums[i-1]；命中答案后两个指针是否用 while 跳过了重复邻居。
2. 提交超时：三数之和八成是没用双指针（写成两层以上循环），或排序后内层没用对撞而仍在枚举。
3. 指针移动方向拿不准：在纸上写一个有序小数组，标出 left/right，算一次和，问自己「要让和变大/变小，只能动哪边」，推三次就有感觉。

面试常问

• 三数之和能不能做到 O(n)？ 不能，基于比较的排序下界是 O(n log n)，而当前最优整体为 O(n²)。若只判断「是否存在」一组解，可以用哈希把内层降到 O(n)，整体仍是 O(n²)，且去重更麻烦；输出全部不重复三元组时排序 + 双指针是标准答法。

• 两数之和 II（输入有序数组）怎么做？ 对撞双指针：小了 left++，大了 right--，O(n) 时间 O(1) 空间。这是三数之和的内层子问题。

• 如果有重复数字但题目不允许去重逻辑太复杂，有什么技巧？ 可以用 Set<List<Integer>> 收结果自动去重，但这是用数据结构掩盖逻辑，面试官可能追问，建议掌握指针跳过法，把 Set 作为兜底方案。

自测三问

1. 对撞型双指针成立的前提条件是什么？
2. 盛水容器移动短边，背后「不会漏掉最优解」的论证你能否复述？
3. 三数之和的两处去重分别在哪？漏了会怎样？

小结一句话

双指针靠「有方向地排除」把多层枚举压成一次扫描：有序配对看和的大小，盛水容器移动短边，三数之和一静两动加两处去重。

延伸

• 巩固练习：LeetCode 167 两数之和 II、LeetCode 283 移动零、LeetCode 18 四数之和
• 把代码提交到本站在线判题平台，专门构造含大量重复值的数组测试去重
• 下一课预告：栈——专治「最近的、未匹配的」一类问题，拿下有效括号与每日温度