LeetCode 热门 100 题之双指针模块精讲（Java 向）

概述

双指针（Two Pointers）是数组与链表类问题中最基础也最强大的算法技巧之一。其核心思想是利用两个指针（通常是索引）以某种策略遍历数据结构，从而将原本需要嵌套循环的 O(n²) 甚至 O(n³) 的暴力解法，优化为 O(n) 的单次遍历。

双指针主要分为两类场景：

左右指针（相向指针）：两个指针分别从数组的两端向中间移动，常用于处理「有序数组中的配对问题」或「区间最值问题」。典型代表是盛最多水的容器和三数之和。
快慢指针（同向指针）：两个指针从同一侧出发，移动速度不同，常用于原地去重、移除元素等。典型代表是移动零。

双指针最大的优势在于时间复杂度低（通常 O(n)）且空间复杂度为 O(1)，不需要额外的数据结构存储中间结果。本文选取 LeetCode 热门 100 题中双指针模块的 4 道经典题目，从暴力解法的缺陷出发，逐步推导双指针的优化思路，并给出完整的 Java 实现。

题目一：283. 移动零

题目简述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例：输入 [0,1,0,3,12]，输出 [1,3,12,0,0]

要求：必须原地修改数组，不能复制额外的数组。

暴力解法

最直观的思路是新建一个数组，遍历原数组将非零元素按顺序放入新数组，最后在末尾补零。但这样做空间复杂度为 O(n)，不符合「原地修改」的要求。

另一种暴力思路是每次遇到零，就将后面的所有元素前移一位，时间复杂度为 O(n²)，效率极低。

优化思路：快慢双指针（同向指针）

核心思想：使用两个指针，一个慢指针指向下一个非零元素应该放置的位置，一个快指针用于遍历数组。

快指针 r 负责扫描整个数组。
慢指针 l 始终指向「已处理区域的下一个位置」，即下一个非零元素应该存放的位置。

每当快指针遇到非零元素，就将其与慢指针指向的位置交换（或赋值），然后慢指针前进一位。遍历结束后，所有非零元素都在数组前端，剩余位置自然全是零。

具体实现步骤

初始化慢指针 l = 0。
快指针 r 从 0 遍历到 n-1：
- 若 nums[r] != 0，将 nums[r] 与 nums[l] 交换，l++。
遍历结束，数组前 l 个位置均为非零元素且保持相对顺序，l 之后均为零。

class Solution {
    public void moveZeroes(int[] nums) {
        int l = 0; // 慢指针：指向下一个非零元素应该放置的位置
        for (int r = 0; r < nums.length; r++) {
            if (nums[r] != 0) {
                // 交换非零元素到前面
                if (l != r) {
                    int temp = nums[l];
                    nums[l] = nums[r];
                    nums[r] = temp;
                }
                l++;
            }
        }
    }
}

复杂度分析

维度	复杂度
时间复杂度	O(n)，仅需一次遍历
空间复杂度	O(1)，仅使用常数额外空间

关键点与易错点

相对顺序的保持：由于慢指针只在遇到非零元素时才前进，且交换操作不改变非零元素之间的相对顺序，因此天然满足题目要求。
原地修改：所有操作都在原数组上进行，没有创建新数组。
交换 vs 赋值：也可以采用「赋值 + 补零」的方式——先将非零元素依次赋值到前面，遍历结束后将剩余位置全部置零。两种方式均可，交换法更简洁。

题目二：11. 盛最多水的容器

题目简述

给定一个长度为 n 的整数数组 height，有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

示例：输入 height = [1,8,6,2,5,4,8,3,7]，输出 49

说明：不能倾斜容器。

暴力解法

遍历所有可能的 (i, j) 组合，计算 min(height[i], height[j]) * (j - i)，记录最大值。

时间复杂度为 O(n²)，当 n 较大时（题目中 n 可达 10⁵）会超时。

优化思路：左右双指针（相向指针）

核心洞察：水的高度由较矮的那条线决定（木桶短板效应）。

初始化左指针 left = 0，右指针 right = n - 1，此时宽度最大。
每次计算当前容器容量，更新最大值。
关键贪心策略：永远移动较矮的那一侧指针。
- 如果移动较高的一侧，宽度减小，高度不可能增加（因为高度由较矮的一侧决定），容量只会更小。
- 移动较矮的一侧，才有机会遇到更高的柱子，从而增大容量。

具体实现步骤

初始化 left = 0，right = height.length - 1，max = 0。
当 left < right 时循环：
- 计算当前容量：min(height[left], height[right]) * (right - left)。
- 更新 max。
- 若 height[left] < height[right]，则 left++；否则 right--。
返回 max。

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

复杂度分析

维度	复杂度
时间复杂度	O(n)，每个元素最多被访问一次
空间复杂度	O(1)，仅使用常数额外空间

关键点与易错点

为什么移动短板而非长板：这是本题最核心的直觉。容量 = 短板高度 × 宽度。移动长板时，短板高度不变（或变小），宽度减小，容量必减。只有移动短板，短板高度才有可能提升。
指针相遇即停止：当 left >= right 时，所有可能的容器都已考察完毕。
与接雨水的区别：盛最多水的容器是选两条线求最大容量；接雨水是利用所有柱子计算总积水量。两者虽都用到左右双指针，但逻辑截然不同。

题目三：15. 三数之和

题目简述

给定一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k、j != k，且 nums[i] + nums[j] + nums[k] == 0。返回所有和为 0 且不重复的三元组。

示例：输入 nums = [-1,0,1,2,-1,-4]，输出 [[-1,-1,2],[-1,0,1]]

注意：答案中不可以包含重复的三元组。

暴力解法

三重循环枚举所有三元组，时间复杂度 O(n³)，且去重非常麻烦。

优化思路：排序 + 双指针

核心思想：先排序，再固定一个数，将问题转化为「两数之和」。

排序后数组有序，可以利用双指针从两端向中间逼近。
固定第一个数 nums[i]，然后在 i+1 到 n-1 的范围内用双指针寻找两个数，使得三数之和为 0。
排序带来的另一个好处是方便去重：跳过相邻的重复元素。

具体实现步骤

对数组进行排序。
外层循环 i 从 0 到 n-3：
- 剪枝：若 nums[i] > 0，由于数组已排序，后续所有数都 >= nums[i] > 0，三数之和必 > 0，直接 break。
- 去重：若 i > 0 且 nums[i] == nums[i-1]，跳过当前 i，避免重复三元组。
- 初始化左指针 l = i + 1，右指针 r = n - 1。
- 当 l < r 时循环：
  - 计算 sum = nums[i] + nums[l] + nums[r]。
  - 若 sum == 0：找到一组解，加入结果集；然后移动 l 和 r 并跳过所有重复值。
  - 若 sum < 0：和太小，l++。
  - 若 sum > 0：和太大，r--。
返回结果集。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length < 3) return ans;

        Arrays.sort(nums);
        int n = nums.length;

        for (int i = 0; i < n - 2; i++) {
            // 剪枝：最小值已大于0，不可能有解
            if (nums[i] > 0) break;
            // 去重：跳过重复的起始值
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    ans.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    // 跳过重复的左值
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    // 跳过重复的右值
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                } else if (sum < 0) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return ans;
    }
}

复杂度分析

维度	复杂度
时间复杂度	O(n²)：排序 O(n log n)，外层循环 O(n)，内层双指针 O(n)，整体 O(n²)
空间复杂度	O(log n) 到 O(n)：排序所需栈空间（取决于排序算法），不计输出空间时为 O(1)

关键点与易错点

排序是前提：双指针在有序数组上才能根据 sum 与 0 的大小关系决定指针移动方向。
去重是难点：需要在外层循环和找到解后两处进行去重。
- 外层：if (i > 0 && nums[i] == nums[i-1]) continue;
- 内层找到解后：while (l < r && nums[l] == nums[l+1]) l++; 和 while (l < r && nums[r] == nums[r-1]) r--;
剪枝优化：if (nums[i] > 0) break; 利用有序数组的特性提前终止。
指针更新：找到解后，在跳过重复值之后，必须执行 l++ 和 r--，否则会陷入死循环。

题目四：42. 接雨水

题目简述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

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

暴力解法

对于每个位置 i，分别向左和向右扫描找到左侧最高柱和右侧最高柱，该位置能接的雨水量为 min(leftMax, rightMax) - height[i]（若为正）。

时间复杂度 O(n²)，空间复杂度 O(1)。

优化思路：左右双指针（相向指针）

核心思想：利用两个指针从两端向中间移动，同时维护左侧最高和右侧最高的柱子高度。

对于位置 i 能否接水，取决于 min(左侧最高, 右侧最高) - height[i]。

双指针的精妙之处在于：我们不需要同时知道左右两侧的最高值，只需要知道当前指针所在一侧的最高值是否小于另一侧。

若 height[left] < height[right]，说明 left 位置的「天花板」由左侧最高决定（因为右侧有更高的柱子），此时可以安全地计算 left 位置的积水量。

具体实现步骤

初始化 left = 0，right = height.length - 1，leftMax = 0，rightMax = 0，water = 0。
当 left < right 时循环：
- 若 height[left] < height[right]：
  - 若 height[left] >= leftMax，更新 leftMax = height[left]。
  - 否则，water += leftMax - height[left]。
  - left++。
- 否则（height[left] >= height[right]）：
  - 若 height[right] >= rightMax，更新 rightMax = height[right]。
  - 否则，water += rightMax - height[right]。
  - right--。
返回 water。

class Solution {
    public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int leftMax = 0;
        int rightMax = 0;
        int water = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    water += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    water += rightMax - height[right];
                }
                right--;
            }
        }
        return water;
    }
}

复杂度分析

维度	复杂度
时间复杂度	O(n)，每个元素最多被访问一次
空间复杂度	O(1)，仅使用常数额外空间

关键点与易错点

为什么 height[left] < height[right] 时能安全计算左侧：因为此时 right 侧存在一个比 left 更高的柱子，所以 left 位置的右侧最高至少是 height[right]，而左侧最高已知为 leftMax。因此 left 位置的水位由 leftMax 决定，可以立即计算。
与「盛最多水的容器」的区别：两者都使用左右双指针从两端向中间移动，但移动条件和计算逻辑完全不同。
- 盛最多水：计算面积，移动较矮指针。
- 接雨水：计算积水量，根据两侧最高值决定移动哪一侧。
初始化边界：leftMax 和 rightMax 初始为 0，因为边界外没有柱子，高度为 0。
积水量的计算：只有当前高度 < 当前侧最高值时才有积水量，否则更新最高值。

总结：双指针模块对比与通用心法

四题对比一览

题目	双指针类型	核心技巧	是否排序	时间复杂度	空间复杂度
283. 移动零	快慢指针（同向）	慢指针指向非零元素放置位置	否	O(n)	O(1)
11. 盛最多水的容器	左右指针（相向）	移动较矮指针，贪心求最大面积	否	O(n)	O(1)
15. 三数之和	左右指针（相向）	排序 + 固定一个数 + 双指针找两数	是	O(n²)	O(log n) ~ O(n)
42. 接雨水	左右指针（相向）	维护左右最高，低侧先计算	否	O(n)	O(1)

双指针通用解题心法

识别题型：数组/链表问题，若暴力解法需要多层循环，优先考虑双指针能否优化。
确定指针类型：
- 同向指针（快慢指针）：适合原地修改、去重、移除元素等场景。
- 相向指针（左右指针）：适合有序数组配对、区间最值、面积/水量计算等场景。
排序是双刃剑：三数之和依赖排序才能使用双指针；但盛最多水和接雨水不需要排序，排序反而会破坏原始位置信息。
明确指针移动条件：双指针的核心是每次只移动一个指针，移动哪个取决于具体问题的逻辑。
- 移动零：快指针遍历，慢指针记录位置。
- 盛最多水：移动较矮的指针。
- 三数之和：根据 sum 与 0 的大小关系移动。
- 接雨水：根据两侧最高值决定移动哪一侧。
空间换时间的对立面：双指针的核心价值在于 O(1) 空间复杂度，在不使用额外数据结构的前提下将时间复杂度从 O(n²) 降至 O(n)。

掌握双指针的精髓，关键在于理解**「指针移动的单调性」**——即每次移动指针都能保证不会错过最优解。这四道题覆盖了双指针最典型的应用场景，吃透它们，足以应对绝大多数双指针类面试题。