Go back

LeetCode Hot 100——双指针篇（相向与快慢双指针）

LeetCode Hot 100 · 双指针篇

双指针是 Hot 100 里性价比最高的一类：代码短、套路清晰、面试官爱问正确性证明。这四道题恰好覆盖了双指针的两个子流派：

相向双指针的核心心法只有一句话：当前状态下，如果某一侧的指针继续参与不可能得到更优解，就把它往中间赶。三题都是同一个思路的不同包装，下面逐个拆。

#283 移动零

题意

给定整数数组 nums，把所有 0 移到末尾，保持非零元素的相对顺序不变，并且必须原地操作（不能复制数组）。

输入：nums = [0,1,0,3,12]
输出：[1,3,12,0,0]

难点与易错点

  1. 原地 + 保持相对顺序，两个约束叠加：如果允许用额外数组，一趟扫描把非零依次放入新数组再补 0 即可，毫无难度；难就难在「原地」和「相对顺序」要同时满足。用错误的原地覆盖（比如左右指针交换，见 905 按奇偶排序）会打乱非零元素的相对顺序——这里必须用同向的快慢指针，而不是相向。
  2. 覆盖 vs 交换的差别：一种写法是「把非零值覆盖到 slow 位置，最后统一把 slow 之后补 0」，另一种是「遇到非零且 slow 处是 0 才交换」。交换法要小心 slow == fast 时把自己和自己交换，所以源材料的实现加了 if (nums[slow] == 0) 的守卫——这个守卫正是「slow 落后于 fast 时 slow 位置必为 0」这一不变式的体现，面试时能说出来会加分。
  3. 边界：全零数组（[0,0,0] 应原样返回，slow 始终不动）；开头就是 0 的数组；已经排好的数组（此时 slow 和 fast 始终同步，不发生交换）。

解法一：暴力 / 直观

新建一个等长数组，第一遍把非零元素按顺序塞到前面，记录个数 cnt，第二遍把剩余位置补 0，最后拷回原数组。

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int[] temp = new int[n]; // 额外数组
        int cnt = 0;
        // 第一遍：按顺序收集所有非零元素
        for (int x : nums) {
            if (x != 0) {
                temp[cnt++] = x;
            }
        }
        // 第二遍：把非零部分拷回原数组（temp 剩余位置默认就是 0）
        for (int i = 0; i < n; i++) {
            nums[i] = temp[i];
        }
    }
}

瓶颈：空间 O(n)，违反题目「原地」的要求，面试直接写这个会被追问优化。它的价值只是把「收集非零 + 补零」的思路讲清楚，为下面的原地覆盖铺路。

解法二：优化 / 最优（快慢指针）

本质是快慢指针原地覆写：慢指针 slow 指向「下一个可放非零元素的位置」，快指针 fast 扫描全数组。

现实类比——捡石头：一条传送带上有普通石头和空石头（0）。你用左手（慢指针）标记下一个放实心石头的位置，右手（快指针）负责扫描，遇到实心石头就搬到左手位置，遇到空石头就跳过。左手只会在右手确认实心后往前挪，所以搬完一遍，实心石头天然排在前半段，空石头自然堆在后半段。

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0; // 慢指针：指向下一个可放非零元素的位置
        int fast = 0; // 快指针：扫描整个数组

        while (fast < nums.length) {
            if (nums[fast] != 0) {
                // 只有 slow 位置是 0 时才需要交换；否则 slow 与 fast 同位置，交换无意义
                if (nums[slow] == 0) {
                    nums[slow] = nums[fast];
                    nums[fast] = 0;
                }
                slow++; // 非零元素已就位，慢指针右移
            }
            fast++; // 快指针始终右移，直到遍历完数组
        }
    }
}

复杂度逐步推导：

另一种更简洁的等价写法是「覆盖 + 末尾补零」：slow 处直接写 nums[fast]，最后把 [slow, n) 补 0。交换法交换次数更少（只在有 0 时才动手），两者都是 O(n)/O(1)，选哪种都行，关键是要能说清「slow 之前全是非零」这条不变式。

💭 思考：为什么「原地 + 保持相对顺序」这两个约束叠加，就决定了必须用「同向」快慢指针？——先想暴力解：开新数组收集非零再补 0，空间 O(n) 违约。要在原地做，又要不改变非零元素的先后，就不能用「相向左右指针交换」（那会把后面的非零换到前面、打乱顺序，那是「无序分区」）。于是只剩一条路：两个同向指针，fast 探路、slow 落子，维护「slow 之前全是非零」这条不变式。看到「原地 + 保持顺序」这个信号，就直接锁定快慢指针，而不是相向指针——两者的取舍全看「顺序是否必要」。

多解法对比

解法时间复杂度空间复杂度适用场景
额外数组O(n)O(n)只求写对、不要求原地；作为讲解铺垫
快慢指针（交换/覆盖）O(n)O(1)题目要求原地；面试标准答案

本题约束是原地 + 保持相对顺序，暴力法的 O(n) 额外空间直接违约，所以最优解锁定快慢指针——它用两个指针把空间压到 O(1)，且不破坏相对顺序。

CodeTop 变体

#11 盛最多水的容器

题意

给定 n 条垂线，第 i 条线端点为 (i, 0) 和 (i, height[i])。任选两条线与 x 轴围成一个容器，求能容纳的最大水量（即最大矩形面积）。

输入：[1,8,6,2,5,4,8,3,7]
输出：49   // 选 height[1]=8 与 height[8]=7，宽度 7，装水 7×7=49

难点与易错点

  1. 贪心正确性是这个题的灵魂：为什么「每次移动较矮的一侧」一定不漏解？这是字节/腾讯最爱追问的证明，代码三行写完，但证不出来照样挂。核心是：面积 = 宽度 × 两侧较矮的高度，宽度随指针靠拢单调递减，所以只有「换掉更矮的板」才可能换来更高的下限、抵消宽度的损失；移动更高的一侧，矮板不变、宽度还变小，面积必然不增。
  2. 容易被「看似单调」带偏：面积既不随宽度单调（高度会变），也不能直接二分或单调栈，不少人想到这层就卡住。正确姿势是抓住「面积由短板决定」这个木桶原理，把问题转化为「淘汰短板」。
  3. 边界：height[left] == height[right] 时移动哪边都行（此时两边一样矮，随便淘汰一个都不影响正确性）；只有两条线时直接返回 min×1；不要忘记用 Math.min 取短板而不是取平均。

解法一：暴力 / 直观

枚举所有两条线的组合 (i, j)，逐个算面积取最大。

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int maxWater = 0;
        for (int i = 0; i < n; i++) {          // 左端点
            for (int j = i + 1; j < n; j++) {  // 右端点
                int water = (j - i) * Math.min(height[i], height[j]);
                maxWater = Math.max(maxWater, water);
            }
        }
        return maxWater;
    }
}

瓶颈：时间 O(n²)，n 到 10⁵ 量级时必超时。它穷举了所有对，但没有利用「短板决定面积」这个结构——很多组合从面积角度一眼就不可能成为答案，这正是可剪枝的地方。

解法二：优化 / 最优（相向双指针 + 贪心）

题目本质：双指针贪心。容积 = 宽度 × 较小高度，宽度随指针靠拢必然减小，因此每次移动较小的那一侧，才可能换来更大的容积。

现实类比——水桶装水：两块木板夹住的水量取决于较短的那块（木桶原理）。我们从最宽的状态（两端）开始，每次把较短的板换掉，看能不能找到更高的板来弥补宽度的损失；如果两块一样高，换哪块都行。

class Solution {
    public int maxArea(int[] height) {
        int left = 0;                     // 左指针从最左出发
        int right = height.length - 1;    // 右指针从最右出发（宽度最大）
        int maxWater = 0;

        while (left < right) {
            // 当前容积 = 宽度 × 两侧最小高度（木桶原理）
            int currentWater = (right - left) * Math.min(height[left], height[right]);
            maxWater = Math.max(maxWater, currentWater);

            // 移动高度较小的指针：保留较高的一侧，才可能找到更大容积
            // 移动较高侧只会让宽度减小而高度不增，必然不优
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxWater;
    }
}

复杂度逐步推导：

为什么移动短板是对的（正确性证明）：设当前 left < right 且 height[left] < height[right]，宽度为 w = right - left。固定 left，让 right 任意左移到 right'，此时面积 = min(height[left], height[right']) × (right' - left) ≤ height[left] × w（宽度变小、短板不高于原短板）。也就是说，只要 left 还是那块短板，right 怎么动都不可能超过当前面积，所以 left 这一侧可以放心淘汰、直接 left++。每步都淘汰一个「不可能更优」的指针，最终不会漏掉最优解。

多解法对比

解法时间复杂度空间复杂度适用场景
暴力枚举O(n²)O(1)n 很小；用于验证正确性
相向双指针O(n)O(1)本题约束（n 可到 10⁵）；标准答案

本题 n 上限通常到 10⁵，O(n²) 会跑到 10¹⁰ 量级直接超时，而双指针 O(n) 一趟扫完，且空间 O(1)，因此最优解必选相向双指针。

CodeTop 变体

#15 三数之和

题意

给定整数数组 nums，找出所有满足 i != j != k 且 nums[i] + nums[j] + nums[k] == 0 的不重复三元组，返回所有这样的三元组（元素顺序任意，但结果集合不能有重复三元组）。

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]   // 注意 [-1,0,1] 只出现一次，尽管 -1 出现两次

难点与易错点

  1. 去重是最大的坑，而且是三层去重，缺一不可：
    • 固定元素去重：i > 0 && nums[i] == nums[i-1] 时跳过，否则 [-1,0,1] 会被两个不同的 -1 各找出一遍。
    • 左指针去重：找到一组解后，while (left < right && nums[left] == nums[left+1]) left++。
    • 右指针去重：while (left < right && nums[right] == nums[right-1]) right--。
    • 初学者常漏掉后两层，或者把「固定元素去重」写成 nums[i] == nums[i+1]（与「后一个」比较是错的，会漏掉 [0,0,0] 这类解）。
  2. [0,0,0] 是经典特例：全 0 数组应返回 [[0,0,0]]。如果去重写错（比如先跳固定元素再用 if 去重），很容易把唯一这组解也跳过。
  3. 边界与剪枝：排序后若 nums[i] > 0，由于数组升序、后面的数只会更大，三数之和不可能为 0，可直接 return；去重用 while 而非 if（连续重复元素不止一个）；访问 nums[left+1] 时必须先判 left < right，否则越界。
  4. 为什么不用哈希表：哈希能 O(n²) 求「两数之和」，但三数之和里处理「三元组去重」极其繁琐（要排序键去重），还容易踩「同一元素复用」的坑，所以排序 + 双指针才是标准答案。

解法一：暴力 / 直观

三重循环枚举所有 (i, j, k)，用 Set 去重（先对三元组排序再入 Set 作为键）。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Set<List<Integer>> set = new HashSet<>(); // 用 Set 去重
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> triple = Arrays.asList(nums[i], nums[j], nums[k]);
                        Collections.sort(triple); // 排序后才能作为去重键
                        set.add(triple);
                    }
                }
            }
        }
        return new ArrayList<>(set);
    }
}

瓶颈：时间 O(n³) 在 n=3000 时已到 10¹⁰ 量级必然超时；而且用「先算出全部、再 Set 去重」的思路很笨，等于把重复的活全干完再回头清理。优化的关键是排序后让重复元素天然相邻，用指针跳过，从源头避免重复。

解法二：优化 / 最优（排序 + 固定 + 双指针）

题目本质：排序后，对每个固定元素 nums[i]，用双指针在其右侧查找两数之和等于 -nums[i] 的组合，同时跳过重复元素避免重复结果。

现实类比——三人拼车凑钱：先把参与者按出资额排好队，固定出资最少的一位，然后让「出资最多的一位」和「出资次少的一位」两个指针从两端往中间凑，凑出剩余金额的组合；凑到了就收下并跳过相同出资额的重复人选，凑多了就减少出资多的那端，凑少了就增加出资少的那端。

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; i++) {
            // 剪枝：排序后最小值已 > 0，三数之和不可能为 0，直接退出
            if (nums[i] > 0) {
                return result;
            }

            // 第一层去重：跳过重复的固定元素，避免结果中出现重复三元组
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;              // 双指针在 i 的右侧查找
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum > 0) {
                    right--; // 三数和偏大，右指针左移减小和
                } else if (sum < 0) {
                    left++;  // 三数和偏小，左指针右移增大和
                } else {
                    // 找到一个合法三元组
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 第二层去重：跳过 left 侧的重复元素
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    // 第三层去重：跳过 right 侧的重复元素
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }

                    // 内缩，继续寻找下一组
                    left++;
                    right--;
                }
            }
        }

        return result;
    }
}

复杂度逐步推导：

💭 思考：为什么「排序 + 双指针」能把三数之和从 O(n³) 降到 O(n²)？——先看暴力为什么慢：三重循环枚举 (i,j,k)，还要靠 Set 去重，等于把重复解全算出来再清理。排序带来两个红利：一是大小关系可用，固定一个数后「两数之和等于 -nums[i]」就退化成双指针对撞（和偏大右指针左移、偏小左指针右移）；二是重复元素天然相邻，用 while 跳过即可从源头避免重复。看到「三数之和 / 四数之和 / 找所有组合」这类「多个数凑定值 + 要去重」的信号，就锁定「排序 + 固定一端 + 相向双指针」这个框架。

多解法对比

解法时间复杂度空间复杂度适用场景
三重循环 + Set 去重O(n³)O(n)n 很小；只求正确
排序 + 固定 + 双指针O(n²)O(1)本题约束（n 可到 3000）；标准答案

本题 n 上限约 3000：暴力 O(n³) ≈ 2.7×10¹⁰ 超时，而排序 + 双指针 O(n²) ≈ 9×10⁶ 轻松通过，且去重在 O(1) 空间内完成，故最优解锁定后者。

CodeTop 变体

#42 接雨水

题意

给定 n 个非负整数表示柱子高度，计算这些柱子按此排列后，下雨能接住多少雨水（每个位置能积的水等于其左右两侧最高柱子中的较矮者减去自身高度）。

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

难点与易错点

  1. 每个位置的接水量公式是核心：水量[i] = min(左侧最大高度, 右侧最大高度) - height[i]，若为负则取 0。这是木桶效应的直接体现——左右最高的墙里较矮的那面决定水位上限。想清楚这一点，所有解法都是它的不同实现。
  2. 双指针的正确性要能讲透：为什么「从 preMax < sufMax 的较小侧结算」是对的？关键是不变式——当 preMax < sufMax 时，left 右侧必然存在一根高度 ≥ sufMax 的墙（就是 right 或者更右边的柱子），因此 left 位置的右侧最大高度一定 ≥ sufMax > preMax，于是 left 处的积水只由 preMax 决定，可以立刻结算、无需知道更右侧的细节。
  3. 边界：首尾两根柱子本身接不到水（其一侧没有墙，min 减自身为 0）；空数组或单根柱子直接返回 0（left < right 循环天然不进入）；preMax/sufMax 要在结算前先更新再计算，否则用旧值会算错。

解法一：暴力 / 直观

对每个位置 i，分别向左、向右扫描找到左最大和右最大，套公式累加。

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int totalWater = 0;
        for (int i = 0; i < n; i++) {
            int leftMax = 0, rightMax = 0;
            // 向左找最高墙
            for (int j = i; j >= 0; j--) {
                leftMax = Math.max(leftMax, height[j]);
            }
            // 向右找最高墙
            for (int j = i; j < n; j++) {
                rightMax = Math.max(rightMax, height[j]);
            }
            totalWater += Math.min(leftMax, rightMax) - height[i];
        }
        return totalWater;
    }
}

瓶颈：时间 O(n²)，n 到 2×10⁴ 就会超时。重复劳动非常明显——每个位置都在重新扫描整个数组求最值，而「左侧最大」「右侧最大」完全可以用一次预处理或双指针一次求出来。

解法二：优化 / 最优（相向双指针 + 前后缀最大值）

题目本质：每个位置能接的水量 = min(左侧最大高度, 右侧最大高度) - 当前高度。用双指针维护前后缀最大值，从较小侧入手可以保证计算正确。

现实类比——盛水的槽：每根柱子能接多少水，取决于左边最高墙和右边最高墙里较矮的那面（木桶效应）。从两端夹逼，较短那侧的最大值已经确定，于是可以直接算出当前柱子的积水，往中间收一格；就像站在两边矮墙上往里看，水只会积到矮墙的高度。

class Solution {
    public int trap(int[] height) {
        int left = 0;              // 左指针
        int right = height.length - 1; // 右指针
        int preMax = 0;            // left 左侧（含 left）已见的最大高度
        int sufMax = 0;            // right 右侧（含 right）已见的最大高度
        int totalWater = 0;

        while (left < right) {
            // 先更新两侧历史最大值，再据此结算
            preMax = Math.max(preMax, height[left]);
            sufMax = Math.max(sufMax, height[right]);

            if (preMax < sufMax) {
                // left 侧较矮：left 位置的积水由 preMax 决定
                // 因为右侧必存在高度 >= sufMax > preMax 的墙，水位被 preMax 卡住
                totalWater += preMax - height[left];
                left++;
            } else {
                // right 侧较矮：right 位置的积水由 sufMax 决定
                totalWater += sufMax - height[right];
                right--;
            }
        }

        return totalWater;
    }
}

复杂度逐步推导：

折中方案（面试也常被要求写）：用两个数组 leftMax[i]、rightMax[i] 预处理「i 左侧/右侧的最大值」，再一趟套公式。它时间 O(n)、空间 O(n)，比双指针更好理解，是「从暴力到双指针」的桥梁——双指针的精髓就是用两个滚动变量替代两个前缀数组，把空间从 O(n) 压到 O(1)。

💭 思考：接雨水怎么一步步从 O(n²) 优化到 O(n)/O(1)？——暴力版对每个位置都左右扫一遍求最值，重复劳动明显；于是想到「左右最大值各预处理一次」的前后缀数组，时间降到 O(n) 但空间 O(n)。再进一步：算 left 位置的水量其实只依赖 preMax，而「右侧必有更高的墙」由 preMax < sufMax 这条不变式保证，根本不需要存整个右后缀数组。于是两个滚动变量就替代了两个数组。看到「每个位置的值由『左右最值』决定」这种结构，就沿着「暴力 → 前缀数组 → 双指针滚动」这条链往上爬，最后的落点是双指针。

多解法对比

解法时间复杂度空间复杂度适用场景
暴力（逐列左右扫描）O(n²)O(1)n 很小；理解公式
前缀/后缀数组O(n)O(n)容易想到、好解释的过渡方案
双指针 + 前后缀最大值O(n)O(1)本题约束；最优空间，标准答案
单调栈O(n)O(n)求「每段凹槽」细节、按层而非按列

本题 n 上限可达 2×10⁴ 甚至更大，暴力 O(n²) 超时；前缀数组 O(n) 已可过，但双指针 O(n)/O(1) 空间更优，且是「用两个变量滚动替代两个数组」的经典技巧，面试官最想看到的是双指针。

CodeTop 变体

小结

题号题目双指针类型核心心法
283移动零快慢指针（同向）slow 落子、fast 探路，原地覆写保持顺序
11盛最多水的容器相向双指针淘汰短板，木桶效应
15三数之和排序 + 相向双指针固定一端，两端夹逼 + 三层去重
42接雨水相向双指针 + 前后缀最值较小侧最大值已定，即可结算

四道题里，283 是快慢指针的「原地覆写」范式，11 / 15 / 42 是相向双指针的三种变形：11 淘汰短板、15 排序后夹逼去重、42 用滚动最值按列结算。它们共同的心法始终是那句——找到「当前状态下不可能更优的那一侧」，把它淘汰掉，O(n²) 就塌缩成了 O(n)。手撕时代码都不长，真正拉开差距的是你能不能把「为什么能淘汰」这条不变式讲清楚。

章末提问

  1. 移动零为什么必须用「同向」快慢指针，而不能用「相向」左右指针？——结论：因为要「保持非零元素相对顺序」，相向交换会把后面的非零元素换到前面、打乱顺序。因为相向指针本质是「无序分区」，只保证 0 在右，不保证非零元素的先后。
  2. 接雨水的双指针凭什么能把前缀/后缀数组省成两个滚动变量？——结论：因为计算 left 位置只需要 preMax，而「右侧必有更高墙」由 preMax < sufMax 这条不变式保证，无需真正存下整个右后缀最大值数组，所以两个变量就替代了两个数组。
  3. 三数之和的复杂度为什么是 O(n²) 而不是 O(n³)？——结论：因为排序后外层固定一个数，内层双指针在剩余区间「相向合拢」，每轮 while 至少移动一个指针，两个指针总共只走 O(n) 步，外层 O(n) × 内层 O(n) = O(n²)；排序的 O(n log n) 被高次项吸收。
Share this post on:
Share this post via WhatsAppShare this post on FacebookShare this post on XShare this post via TelegramShare this post on PinterestShare this post via email
Previous Post
二叉树遍历——前序、中序、后序、层序的递归与迭代模板
Next Post
二分查找的8种变体——不只是找等于target