双指针算法详解

从暴力枚举到线性优化 —— 深入理解对撞指针、快慢指针与滑动窗口，掌握算法面试中的高频考点。

什么是双指针

双指针（Two Pointers）并不是一种"数据结构"，而是一种算法设计技巧。它的核心思想是：在遍历数组、链表或字符串等线性结构时，使用两个"指针"（即索引或引用）协同移动，从而将原本需要嵌套循环的 O(n²) 时间复杂度降低到 O(n)。

想象一下这样一个场景：你有一个已经排好序的数组，需要找出两个数使它们的和等于目标值。最直觉的做法是两层 for 循环枚举所有组合，时间复杂度 O(n²)。但如果你从数组两端各放一个指针，每次根据当前和与目标值的大小关系决定移动左指针还是右指针，就能在 O(n) 时间内完成。这就是双指针的精髓 —— 通过指针的协同移动来"剪枝"，避免不必要的枚举。

什么时候考虑使用双指针？

• 数据是有序的（或可以排序后求解），需要查找满足某个条件的元素对。
• 需要在一个循环中同时追踪两个位置（比如数组的两端、快慢两个进度）。
• 问题涉及子数组、子串或区间，且可以通过维护一个窗口的左右边界来解决。
• 链表问题中需要找中点、检测环、找倒数第 k 个节点等。

双指针的三大分类

根据指针的起始位置和移动方向，双指针可以归纳为以下三种常见模式：

对撞指针

对撞指针（Opposite Direction Two Pointers）是最直观的双指针模式：左指针 left 从数组起始位置（索引 0）出发，右指针 right 从数组末尾（索引 n-1）出发，两者相向而行，直到相遇或满足某个终止条件。

对撞指针通常适用于有序数组的场景，因为我们可以根据当前两个指针指向的元素值与目标值的关系来判断应该移动哪个指针 —— 这正是"有序"带来的信息增益。

基本模板

function twoPointerTemplate(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left < right) {
        const sum = arr[left] + arr[right];
        if (sum === target) {
            return [left, right];   // 找到答案
        } else if (sum < target) {
            left++;                  // 和太小，左指针右移增大和
        } else {
            right--;                 // 和太大，右指针左移减小和
        }
    }
    return null;                     // 未找到
}

这个模板的复杂度分析：时间复杂度 O(n)（每个元素最多被访问一次），空间复杂度 O(1)（只用了两个额外的指针变量）。

例题：两数之和 II —— 输入有序数组

这是对撞指针最经典的入门题目，来自 LeetCode 167。

题目描述

给定一个已按非递减顺序排列的整数数组 numbers，请你从数组中找出两个数，使它们的和等于目标数 target。返回这两个数的索引（从 1 开始计数）。你可以假设每个输入只对应唯一的答案，且不能重复使用同一个元素。

解题思路

数组已经排好序了，这是关键前提。我们使用对撞指针：

1. 初始化 left = 0，right = numbers.length - 1。
2. 计算 sum = numbers[left] + numbers[right]。
3. 如果 sum === target，返回 [left + 1, right + 1]（题目要求 1-based 索引）。
4. 如果 sum < target，说明需要更大的和，左指针右移：left++。
5. 如果 sum > target，说明需要更小的和，右指针左移：right--。

function twoSum(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;

    while (left < right) {
        const sum = numbers[left] + numbers[right];
        if (sum === target) {
            return [left + 1, right + 1];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return [-1, -1]; // 根据题目保证，不会执行到这里
}

以 numbers = [2, 7, 11, 15], target = 9 为例：初始时 left 指向 2，right 指向 15，和为 17 > 9，右指针左移到 11；和为 13 > 9，右指针继续左移到 7；和为 9，命中目标，返回 [1, 2]。整个过程只用了 3 步，而暴力枚举需要 6 步。当数组规模更大时，O(n) 对 O(n²) 的优势会更加显著。

例题：盛最多水的容器

这道题来自 LeetCode 11，是对撞指针的另一个经典应用，但其决策逻辑比两数之和更加微妙。

题目描述

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

解题思路

容器的水量由两个因素决定：两条线之间的宽度（right - left）和两条线中较短的那条的高度（min(height[left], height[right])）。桶的短板效应 —— 水量取决于较矮的那条线。

对撞指针策略：

1. 从两端开始，计算当前容器的水量。
2. 更新最大水量。
3. 移动较短的那条线对应的指针 —— 因为如果移动较高的那条线，宽度减小而高度不会增加（短板不变），水量只会变小。只有移动较短的那条线，才有可能在宽度减小的同时提升高度，从而获得更大的水量。

function maxArea(height) {
    let left = 0;
    let right = height.length - 1;
    let maxWater = 0;

    while (left < right) {
        const width = right - left;
        const h = Math.min(height[left], height[right]);
        const area = width * h;
        maxWater = Math.max(maxWater, area);

        // 移动较短的那条线
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxWater;
}

这个算法的精妙之处在于：每次移动都"放弃"了所有以当前较短线段为一端、且另一端在它和另一指针之间的所有组合。这些组合的宽度更小、高度受限于这个较短的线，面积不可能更大，因此可以安全地"剪"掉。时间复杂度 O(n)，空间复杂度 O(1)。

快慢指针

快慢指针（Fast & Slow Pointers）是指两个指针从同一位置出发、以不同的速度同向移动。最常见的设定是慢指针每次移动一步、快指针每次移动两步。

快慢指针的核心用途分为两类：

• 链表问题：Floyd 判圈算法（检测链表是否有环）、找链表的中点、找倒数第 k 个节点。
• 数组问题：寻找重复数（将数组视为链表）、原地去重（一个指针负责遍历，另一个负责维护"有效区域"的边界）。

Floyd 判圈算法的原理

如果有环，快慢指针一定会相遇。为什么？可以把环想象成一个圆形跑道，快指针每次比慢指针多走一步，相对速度为 1 步/次。只要环存在，快指针就会以每次一步的相对速度逐渐追上慢指针，不存在"跳过"的可能。从数学上看，设链表头到环入口的距离为 a，环的长度为 b，当慢指针进入环时快指针已经在环内走了若干圈，之后快指针最多需要 b 步就能追上慢指针。

例题：环形链表检测

这是快慢指针最经典的应用，来自 LeetCode 141。

题目描述

给你一个链表的头节点 head，判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达，则链表中存在环。

解题思路

使用 Floyd 判圈算法（也叫"龟兔赛跑"算法）：

1. 初始化慢指针 slow = head，快指针 fast = head。
2. 每次迭代，慢指针走一步（slow = slow.next），快指针走两步（fast = fast.next.next）。
3. 如果快指针或快指针的 next 为 null，说明链表有终点，无环。
4. 如果快慢指针相遇（slow === fast），说明有环。

function hasCycle(head) {
    if (!head || !head.next) return false;

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            return true;   // 相遇，有环
        }
    }
    return false;          // 快指针到达终点，无环
}

时间复杂度 O(n)（无环时快指针遍历所有节点；有环时最多走 n + b 步，其中 b 为环长），空间复杂度 O(1)（不需要额外的哈希表来记录访问过的节点）。相比之下，用哈希表记录已访问节点的解法虽然直观，但需要 O(n) 的额外空间。

滑动窗口

滑动窗口（Sliding Window）可以看作是双指针的一种特殊形式，左右指针维护一个"窗口"（即子数组或子串），通过移动右指针来扩展窗口、移动左指针来收缩窗口。滑动窗口尤其擅长处理子串、子数组相关的问题，因为它能够在线性时间内枚举所有满足条件的连续区间。

固定窗口 vs 可变窗口

• 固定大小窗口：窗口长度固定为 k，左右指针同步移动（left++, right++），常用于求大小为 k 的连续子数组的最大/最小和或平均值。
• 可变大小窗口：窗口大小动态变化，右指针不断扩展窗口直到满足条件，左指针随后收缩窗口直到条件不满足，在此过程中记录最优解。这是滑动窗口最常见的形态。

可变窗口模板

function slidingWindow(s) {
    let left = 0;
    let right = 0;
    let maxLen = 0;
    const window = new Map();   // 或 Set / 数组，视需求而定

    while (right < s.length) {
        const c = s[right];
        right++;                // 扩展窗口：右指针右移，加入新元素
        // 更新窗口数据（如 window.set(c, count)）

        // 收缩窗口：当窗口不满足条件时，移动左指针
        while (/* 窗口不满足条件 */) {
            const d = s[left];
            left++;             // 收缩窗口：左指针右移，移除元素
            // 更新窗口数据（如 window.delete(d)）
        }

        // 此时窗口满足条件，更新答案
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}

模板的精髓在于：right 指针负责"探索"（每次循环都右移一位），left 指针负责"满足约束"（在内部 while 中不断右移直到窗口合法）。这样可以保证每个元素最多被访问两次（被 right 加入一次、被 left 移除一次），整体时间复杂度保持 O(n)。

例题：无重复字符的最长子串

这是滑动窗口最经典的题目，来自 LeetCode 3。

题目描述

给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。

解题思路

维护一个滑动窗口，窗口内的所有字符都是不重复的。用哈希表（Map）记录窗口内每个字符的索引位置。

1. 右指针遍历字符串，每次将当前字符纳入窗口。
2. 如果当前字符已经在窗口内出现，则将左指针移动到上次出现位置的下一位（跳过重复的字符）。
3. 每次迭代都更新最长子串的长度。

function lengthOfLongestSubstring(s) {
    const map = new Map();  // 字符 -> 最新索引
    let left = 0;
    let maxLen = 0;

    for (let right = 0; right < s.length; right++) {
        const char = s[right];

        // 如果字符已在窗口内，收缩左边界
        if (map.has(char) && map.get(char) >= left) {
            left = map.get(char) + 1;
        }

        map.set(char, right);                  // 更新字符的最新位置
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

以 s = "abcabcbb" 为例跟踪：

• right=0, char='a', left=0, 窗口 "a", maxLen=1
• right=1, char='b', left=0, 窗口 "ab", maxLen=2
• right=2, char='c', left=0, 窗口 "abc", maxLen=3
• right=3, char='a', 'a' 在上次索引 0 处出现，left 跳到 1, 窗口 "bca", maxLen=3
• right=4, char='b', 'b' 在上次索引 1 处出现（>=left=1），left 跳到 2, 窗口 "cab", maxLen=3
• 以此类推，最终 maxLen=3

注意判断条件 map.get(char) >= left：仅仅检查 map 中是否存在该字符是不够的，因为 map 中可能保留了窗口之外的旧索引。比如 right 走到第二个 'a' 时，第一个 'a' 已经在 left 左侧了，它在 map 中的旧索引不应该再影响窗口的合法性判断。

双指针适用场景总结

掌握了以上三种双指针模式后，面对新问题时可以从以下几个维度判断是否适用双指针：

场景速查表

核心心法

1. 先排序：很多看上去不能用双指针的问题，排序后就豁然开朗。排序本身需要 O(n log n)，但如果排序后能用 O(n) 的双指针代替 O(n²) 的暴力枚举，总体仍然是划算的。三数之和（LC 15）就是一个经典的"先排序 + 固定一个 + 对撞指针"的组合套路。
2. 循环不变量：设计双指针算法时，想清楚"循环中始终维持什么条件"。对撞指针的循环不变量是"答案一定在 [left, right] 区间内"；滑动窗口的循环不变量是"窗口内的子串/子数组始终满足（或不满足）某个性质"。
3. 移动决策：每次循环中应该移动哪个指针？这是双指针算法设计中最关键的一步。想清楚"移动这个指针后，能排除哪些不可能的选项"，就能建立正确的决策逻辑。
4. 边界处理：双指针的终止条件、空数组/单元素数组的特殊情况、索引越界等都需要仔细处理。尤其是快慢指针中 fast.next.next 的空指针检查。

推荐练习路线

建议按以下顺序刷题巩固双指针技巧：

1. 入门：两数之和 II (LC 167)、验证回文串 (LC 125)、移动零 (LC 283)
2. 进阶：盛最多水的容器 (LC 11)、三数之和 (LC 15)、无重复字符的最长子串 (LC 3)
3. 挑战：接雨水 (LC 42)、最小覆盖子串 (LC 76)、环形链表 II (LC 142)、寻找重复数 (LC 287)