算法面试突击手册 —— 双指针

一、概念与特点

大白话 + 类比

双指针 = 两个人从不同方向/速度走一条路

想象一条笔直的马路上，安排两个人走路：

对撞指针：一个从起点出发，一个从终点出发，两人相遇时问题解决。就像两个人从两端往中间吃一根面条。

快慢指针：一个人走两步，另一个人走一步，快的追上慢的时候，就发现了什么规律。就像在操场上，跑得快的总会套圈跑得慢的。

左右指针：两个人站在数组两端，根据某种条件决定谁往中间移动一步。

本质上，双指针是用 两个位置变量 替代二重循环中的一层，将 O(n²) 降到 O(n)。

核心特征（什么时候该想到用它）

特征	说明
有序数组	排序后可以用对撞指针一次扫描
找两个元素	两数之和、三数之和等组合问题
原地修改	移动零、删除重复、颜色分类
链表判圈	快慢指针检测环
接雨水类	左右指针维护边界信息

识别信号词

“两数之和”、“三数之和”、“最接近的三数之和” → 排序 + 对撞指针
“原地”、“不额外空间”、“移动” → 快慢指针 / 读写指针
“回文”、“反转” → 对撞指针
“环形链表”、“是否有环” → 快慢指针
“盛水”、“接雨水” → 左右夹逼

二、应用场景

三大双指针套路

类型	模式	典型应用
对撞指针	`left=0, right=n-1`，根据条件向中间移动	3Sum, 盛水
快慢指针	`slow=0, fast=0`，fast 探路 slow 记录	移动零, 删重复, 环形链表
左右边界	`left=0, right=n-1`，各自维护一个状态	接雨水

核心模板

// 对撞指针模板
int left = 0, right = nums.length - 1;
while (left < right) {
    if (条件A) left++;
    else if (条件B) right--;
    else { /* 处理 */ }
}

// 快慢指针模板
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
    if (满足条件) {
        nums[slow] = nums[fast]; // 或者交换
        slow++;
    }
}

三、Hot 100 精讲题目

283. Move Zeroes 移动零

📌 给定数组 nums，将所有 0 移到末尾，同时保持非零元素的相对顺序。必须原地操作。

🔍 解题分析

为什么用双指针：需要原地重排，“非零元素保持顺序”说明需要稳定的搬运。

核心思路（类比 = 搬家时把好东西往前放）：

slow 指针指向”下一个非零元素应该放的位置”
fast 指针遍历数组
当 fast 遇到非零元素，就和 slow 位置交换，然后 slow 前进
最终 slow 左边全是非零，slow 右边全是零

易错点：用交换而不是直接赋值，直接赋值会丢失 slow 位置原来的值。

✅ 完整 Java 实现

public void moveZeroes(int[] nums) {
    // slow 指向下一个非零元素应该放的位置
    int slow = 0;

    for (int fast = 0; fast < nums.length; fast++) {
        // fast 探路：发现非零元素就搬到前面
        if (nums[fast] != 0) {
            // 交换 slow 和 fast 位置的元素
            int temp = nums[slow];
            nums[slow] = nums[fast];
            nums[fast] = temp;
            slow++; // 非零区扩大一位
        }
    }
    // 循环结束，slow 及其之前都是非零，之后都是零
}

⏱ 复杂度分析

时间复杂度：O(n)，每个元素访问一次
空间复杂度：O(1)，原地操作

💡 记忆口诀

“fast 探路找非零，slow 留守接应它”

11. Container With Most Water 盛最多水的容器

📌 数组 height 的每个元素代表一根垂直线的高度。找出两条线，与 x 轴一起构成的容器能盛最多的水。如 [1,8,6,2,5,4,8,3,7] → 49

🔍 解题分析

为什么用双指针：暴力枚举所有组合是 O(n²)。但对撞指针可以根据”短板效应”安全地排除不可能更大的情况。

核心思路：

left 在开头，right 在末尾
计算当前水量 = min(height[left], height[right]) × (right - left)
关键决策：谁短谁移动。因为水量由短板决定，只有移动短板才有机会让水量变大
更新全局最大水量

为什么”谁短移谁”安全：如果你移动长板，宽度减小了，高度最多还是短板的高度（因为长板变矮可能更差，长板变高不受影响因为短板才是瓶颈），所以水量不可能增加。只有移动短板才有可能碰到更高的板。

✅ 完整 Java 实现

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxWater = 0;

    while (left < right) {
        // 当前容器的水量 = 短板高度 × 宽度
        int water = Math.min(height[left], height[right]) * (right - left);
        maxWater = Math.max(maxWater, water);

        // 核心：谁短谁移动，因为只有换掉短板才有机会变大
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxWater;
}

⏱ 复杂度分析

时间复杂度：O(n)，每个元素最多访问一次
空间复杂度：O(1)

💡 记忆口诀

“左右夹逼看短板，谁短谁往中间赶”

15. 3Sum 三数之和

📌 判断是否存在三个元素 a, b, c 使 a+b+c=0。找出所有不重复的三元组。如 [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]]

🔍 解题分析

为什么用双指针：三重循环是 O(n³)。排序后固定一个数，剩下两个数就成了 Two Sum，可以用对撞指针 O(n) 解决。

核心思路（一步步拆解）：

排序：让相同元素相邻，方便去重，也启用对撞指针
固定一个数 nums[i]，在 i 右边区间用对撞指针找 target = -nums[i]
去重是关键：
- i 的去重：如果 nums[i] == nums[i-1]，跳过（避免重复三元组）
- left/right 的去重：找到一组解后，left 跳过所有相同值，right 也跳过
根据三数之和与 0 的关系移动指针

易错点：

去重要挪到重复值的最后一个，否则会漏解
找到一组解后要同时移动 left 和 right

✅ 完整 Java 实现

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++) {
        // 剪枝：最小的数都大于 0，后面不用看了
        if (nums[i] > 0) break;

        // i 去重：跳过重复的固定值
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1, right = nums.length - 1;
        int target = -nums[i]; // 要找到的两个数之和

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

            if (sum == target) {
                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--;
            } else if (sum < target) {
                left++;  // 和太小，left 右移变大
            } else {
                right--; // 和太大，right 左移变小
            }
        }
    }

    return result;
}

⏱ 复杂度分析

时间复杂度：O(n²)，外层 n，内层对撞 O(n)
空间复杂度：O(1)（不算结果列表）

💡 记忆口诀

“排序固定一个点，剩下两个左右夹；去重三处要注意，跳过相同把解挖”

42. Trapping Rain Water 接雨水

📌 给定柱子高度数组，计算下雨后能接多少雨水。如 [0,1,0,2,1,0,1,3,2,1,2,1] → 6

🔍 解题分析

为什么用双指针：每个柱子能接的水 = min(左边最高, 右边最高) - 自身高度。如果知道所有位置的 leftMax 和 rightMax，一遍就出结果。但双指针可以用 O(1) 空间动态维护这两个值。

核心思路（类比 = 两边有墙挡水）：

left=0, right=n-1，用 leftMax 和 rightMax 记录左右见过的最高墙
关键：哪个方向的当前最大高度小，就处理哪边的指针
因为左边最大高度 < 右边最大高度时，left 位置的接水量由 leftMax 决定（右边有更高的墙兜底）
处理完就移动该指针，更新它的 max

直观理解：水位由矮的那面墙决定。如果左边墙矮，那就从左边开始灌水，灌到左边墙的高度为止。

✅ 完整 Java 实现

public int trap(int[] height) {
    if (height.length == 0) return 0;

    int left = 0, right = height.length - 1;
    int leftMax = 0, 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)

💡 记忆口诀

“哪边墙矮处理哪边，积水全靠矮墙兜底”

75. Sort Colors 颜色分类

📌 数组包含 0（红）、1（白）、2（蓝），原地排序使得相同颜色相邻，按红白蓝顺序排列。

🔍 解题分析

为什么用双指针：这是经典的荷兰国旗问题，用三个指针实现三路快排。

核心思路（类比 = 三个分区逐渐扩张）：

p0 指向 0 应该放的位置（从 0 开始）
p2 指向 2 应该放的位置（从 n-1 开始）
curr 遍历数组：
- 遇到 0：和 p0 交换，p0++，curr++（换过来的一定是 1，可以放心前进）
- 遇到 1：不用交换，curr++
- 遇到 2：和 p2 交换，p2—，curr 不动（换过来的可能是 0 或 1，需要再判断）

易错点：遇到 2 交换后 curr 不能前进！因为从 p2 换来的元素还没检查过。

✅ 完整 Java 实现

public void sortColors(int[] nums) {
    int p0 = 0;           // 0 的分界线，[0, p0) 全是 0
    int p2 = nums.length - 1; // 2 的分界线，(p2, n-1] 全是 2
    int curr = 0;         // 当前检查的位置

    while (curr <= p2) {  // 注意边界：curr 超过 p2 就结束
        if (nums[curr] == 0) {
            // 遇到 0，换到前面去
            swap(nums, curr, p0);
            p0++;
            curr++; // 换过来的一定 <= 1，放心走
        } else if (nums[curr] == 2) {
            // 遇到 2，换到后面去
            swap(nums, curr, p2);
            p2--;
            // curr 不能走！换过来的东西还没检查
        } else {
            // 遇到 1，正好在中间，不用动
            curr++;
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

⏱ 复杂度分析

时间复杂度：O(n)，每个元素最多被操作一次
空间复杂度：O(1)

💡 记忆口诀

“零前二后一不动，换二回头看一眼”

🔜 上一章：01-哈希表 | 下一章：03-滑动窗口

算法手册 02 双指针

算法面试突击手册 —— 双指针

一、概念与特点

大白话 + 类比

核心特征（什么时候该想到用它）

识别信号词

二、应用场景

三大双指针套路

核心模板

三、Hot 100 精讲题目

283. Move Zeroes 移动零

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀

11. Container With Most Water 盛最多水的容器

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀

15. 3Sum 三数之和

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀

42. Trapping Rain Water 接雨水

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀

75. Sort Colors 颜色分类

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀