双指针

数组与字符串 ⭐⭐ 中级 🔥 高频

💡 核心要点

双指针的本质是用两个位置变量维护一个相对关系。左右指针从两端向中间靠拢，快慢指针从同侧同向移动。关键是明确两个指针分别承担什么语义、什么时候移动哪一个。

识别信号

看到以下模式时，优先考虑双指针：

有序数组上找配对/目标和 → 左右指针（两端夹逼）
原地删除 / 去重 / 分区 / 移动元素 → 快慢指针（slow 维护有效区）
回文串判断 / 反转数组 → 左右指针（对称交换）
合并两个有序数组（从后往前） → 双指针（避免覆盖）
链表找环 / 找中点 → 快慢指针（步长不同）

反例——不适合双指针的场景：

无序数组上找配对：数组无序时，左右指针无法利用单调性剪枝，仍需排序或哈希表
需要回退指针的问题：双指针成立的前提是每个指针单向移动，一旦需要回退就失去 O(n) 优势
多个约束同时变化：三个或更多指针互相影响时，框架会退化，需要其他方法

通用思考框架

双指针不是一个模板，而是一种思维方式。每次遇到新题时按以下四步分析，可以系统地推导出正确解法。

第一步：判断用哪种指针

场景	指针类型	核心原因
有序数组 + 找配对/和/差	左右指针	有序性保证：left 右移 → 和变大；right 左移 → 和变小。两端夹逼可以穷举所有可能而不重不漏
原地修改数组（删除/去重/移动）	快慢指针	slow 维护"已处理有效区"，fast 扫描"待决策区"。两区不重叠，结果直接写回原数组
回文 / 对称 / 反转	左右指针	对称结构天然需要从两端向中心收缩
链表环 / 中点	快慢指针	步长差造成相对位移，Floyd 判环或快指针先走 n 步都依赖此机制

判断关键问题： 问题是否具有单调性？即"当一个指针移动之后，另一个指针是否永远不需要回退"。若答案是否，双指针不适用。

第二步：明确指针语义

在写任何一行代码之前，先用一句话定义每个指针代表什么，以及它维护的不变量（invariant）是什么。

左右指针的语义：

left 指向当前考虑的左候选值（较小端）
right 指向当前考虑的右候选值（较大端）
不变量：答案一定在 [left, right] 区间内（否则已通过单调性排除）

快慢指针的语义：

slow 指向有效区域的边界，[0, slow) 是已确认保留的元素
fast 是探索指针，扫描每一个未决定的元素
不变量：fast 扫过的元素已经被分类（保留 → 写入 slow 位置 / 丢弃 → 跳过）

语义一旦确定，移动逻辑几乎是自动推导出来的——违反不变量就移动对应指针。

第三步：确定移动条件

左右指针的移动逻辑（以目标和为例）：

sum == target：找到答案，记录后视题目决定是否继续（找所有解则同时移动两端）
sum < target：当前和太小，需要增大 → left++（因为数组有序，left 右移使和变大）
sum > target：当前和太大，需要减小 → right--

每次只移动一个指针，保证另一端的信息不丢失。这是双指针 O(n) 复杂度的根本原因。

快慢指针的移动逻辑：

fast 每轮无条件前进一步（扫描每个元素）
只有当 nums[fast] 满足保留条件时，才将其写入 nums[slow] 并推进 slow
否则 slow 静止，fast 继续向前，相当于"跳过"不需要的元素

第四步：确定循环终止条件

左右指针： 循环条件是 left < right（严格小于）。

原因：left == right 时两个指针指向同一元素，不可能构成合法的配对（单个元素无法与自身配对），所以此时已无需继续。

快慢指针： 循环条件是 fast < nums.length。

原因：fast 必须扫描完所有元素才能保证没有遗漏。slow 的终止位置就是有效区域的长度（或最后一个有效元素的下标，取决于具体语义）。

左右指针完整模板：

java

public void leftRightPointer(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        if (/* 找到目标 */) {
            // 记录结果
            left++;
            right--;  // 若只需一个答案，直接 return
        } else if (/* 需要增大 */) {
            left++;
        } else {
            right--;
        }
    }
}

快慢指针完整模板：

java

public int fastSlowPointer(int[] nums) {
    int slow = 0;  // [0, slow) 是已确认保留的有效区
    for (int fast = 0; fast < nums.length; fast++) {
        if (/* nums[fast] 满足保留条件 */) {
            nums[slow] = nums[fast];
            slow++;
        }
        // 不满足则 fast 前进，slow 不动（相当于跳过）
    }
    return slow;  // 有效区域长度
}

典型例题：两数之和 II（LeetCode 167）

题目链接

给定一个升序排列的整数数组 numbers，找到两个数使得它们的和等于目标值 target。返回两个数的下标（1-indexed），保证恰好有一个解。

1. 识别——为什么是左右指针？

数组有序，且要找一对数满足目标和。有序性提供了单调性：numbers[left] + numbers[right] 的值随 left 右移而增大，随 right 左移而减小。因此可以用两端夹逼，每步排除至少一个候选，不需要回退指针。

2. 指针语义

left：当前考虑的左端（较小值）候选，初始为 0
right：当前考虑的右端（较大值）候选，初始为 numbers.length - 1
不变量：若解存在，它的两个下标一定满足 left <= idx1 < idx2 <= right

3. 移动逻辑

计算 sum = numbers[left] + numbers[right]：

sum == target：找到答案，直接返回
sum < target：当前和不够大，需要更大的左值 → left++
sum > target：当前和过大，需要更小的右值 → right--

每步移动后，已排除的区域不包含任何解（可以通过反证法验证），所以不会漏解。

4. 完整代码

java

public int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return new int[]{left + 1, right + 1};  // 1-indexed
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[]{-1, -1};  // 题目保证有解，不会走到这里
}

5. 复杂度

时间：O(n)，left 和 right 各最多移动 n 次，总移动次数 ≤ 2n
空间：O(1)，只用了两个指针变量

延伸题目

题号	题名	难度	关键差异	一句话提示
125	验证回文串	简单	需要跳过非字母数字字符，移动前先用 while 跳过无效字符	左右指针，比较前先跳过非字母数字
11	盛最多水的容器	中等	移动较短边而非较长边——移动较长边只会让面积变小，移动较短边才可能变大	每次移动高度较小的那一侧指针
15	三数之和	中等	三元组：外层固定一个数，内层对剩余区间用左右指针；需要跳过重复元素避免输出重复三元组	排序后固定 i，[i+1, n-1] 区间用左右指针，结果去重
26	删除有序数组中的重复项	简单	快慢指针：`slow` 指向最后一个保留元素，`fast` 遇到不同于 `slow` 的值才推进 slow	`nums[fast] != nums[slow]` 时才写入并推进 slow
27	移除元素	简单	快慢指针：保留条件是 `nums[fast] != val`，比 LC26 更简单，slow 从 0 开始直接覆盖	跳过等于 val 的元素，其余前移
283	移动零	简单	快慢指针先把非零元素前移（同 LC27 逻辑），再把 `[slow, n-1]` 全填 0；不能直接交换否则顺序可能乱	非零元素前移后，尾部区间补零
344	反转字符串	简单	左右指针交换，但操作是 swap 而不是比较——循环体与找配对完全不同	左右指针互换字符，直到相遇
88	合并两个有序数组	简单	从后往前双指针：正向写会覆盖 nums1 未读元素，从大到小写入尾部可以避免覆盖	两个指针从各自末尾出发，大的先放到 nums1 末尾

常见陷阱与调试

左右指针陷阱：

忘记检查数组是否有序：左右指针的单调性依赖有序性，无序数组必须先排序（如 LC15 三数之和的第一步）
三数之和漏掉去重：外层 i 循环和内层 left/right 找到答案后，都需要跳过相邻重复元素，否则结果集包含重复三元组
循环条件写成 left <= right：left == right 时两指针指向同一元素，不构成合法配对，应该用严格小于

快慢指针陷阱：

slow 语义不统一：有时 slow 指向下一个写入位置（返回 slow），有时指向最后一个有效元素（返回 slow + 1）。写代码前先确定语义，不要混用
LC26 的 slow 初始值：slow = 0 并且 fast 从 1 开始（因为第一个元素一定保留），如果 fast 也从 0 开始会导致自己覆盖自己
移动零时直接交换：快慢指针交换（swap）和覆盖（覆盖写）在移动零问题中结果可能不同——用交换会把零和非零元素互换位置，若数组有多个零则顺序正确；但更清晰的做法是先覆盖再补零

调试思路：

在纸上画出指针初始位置，手动模拟 2-3 步
检查循环不变量：每次循环开始时，不变量是否成立？
验证边界：空数组、单元素数组、全相同元素数组是否正确处理？

面试常问 & 怎么答

双指针和暴力枚举的区别？

暴力枚举是两层循环 O(n²)。双指针利用数组的有序性或单调性，让两个指针各自单向移动，总共只扫描 O(n)。前提是问题具有单调性——当一个指针移动后，另一个指针不需要回退。如果没有单调性，双指针可能漏解，不能使用。

快慢指针的 slow 指什么？

slow 永远指向已处理区域的边界。[0, slow) 是有效区域（已确认保留的元素），fast 负责探索未处理部分。面试时先说清楚 slow 的语义（"slow 是下一个写入位置"还是"slow 是最后一个有效元素的下标"），再写代码，返回值自然就对了。

如何证明双指针不会漏解？

以左右指针找目标和为例：每次移动 left 时，意味着 numbers[left]（旧值）与 [left+1, right] 内任何元素的配对都已被排除（因为当前 sum < target，右端已经是最大值，换更小的右端只会更小，所以 numbers[left] 和任何剩余元素都不可能凑成目标和）。类似地，移动 right 也可反证。这就是不漏解的证明思路。

看到什么就先想到这类

"有序数组 + 两数之和/配对" → 左右指针
"原地删除 / 去重 / 移动元素" → 快慢指针
"回文串判断 / 反转数组" → 左右指针
"合并两个有序数组" → 从后往前双指针
"三数之和 / 四数之和" → 排序 + 固定外层 + 内层左右指针

双指针 ​

识别信号 ​

通用思考框架 ​

第一步：判断用哪种指针 ​

第二步：明确指针语义 ​

第三步：确定移动条件 ​

第四步：确定循环终止条件 ​

典型例题：两数之和 II（LeetCode 167） ​

1. 识别——为什么是左右指针？ ​

2. 指针语义 ​

3. 移动逻辑 ​

4. 完整代码 ​

5. 复杂度 ​

延伸题目 ​

常见陷阱与调试 ​

面试常问 & 怎么答 ​

双指针和暴力枚举的区别？ ​

快慢指针的 slow 指什么？ ​

如何证明双指针不会漏解？ ​

看到什么就先想到这类 ​

双指针

识别信号

通用思考框架

第一步：判断用哪种指针

第二步：明确指针语义

第三步：确定移动条件

第四步：确定循环终止条件

典型例题：两数之和 II（LeetCode 167）

1. 识别——为什么是左右指针？

2. 指针语义

3. 移动逻辑

4. 完整代码

5. 复杂度

延伸题目

常见陷阱与调试

面试常问 & 怎么答

双指针和暴力枚举的区别？

快慢指针的 slow 指什么？

如何证明双指针不会漏解？

看到什么就先想到这类