双指针法专题导读

双指针不是一种数据结构，而是一种用两个位置变量协同缩小搜索范围的思考方式。它的知识点散落在数组、字符串、链表、哈希各专题里，本专题导读的任务是把它们串成体系：四种形态、各自的适用信号，以及写代码前必须想清楚的不变量。

四种形态总览

对撞指针：有序与对称的产物

left 从左侧、right 从右侧出发，根据比较结果决定移动哪一侧。看到两个信号就该想到它：

• 有序：排序后两侧之和偏大移 right、偏小移 left，一次移动排除一整批候选。
• 对称：反转、回文判断天然是"两侧交换/比较"。

它的正确性根基是一个不变量：每移动一次指针，被跳过的元素都不可能出现在答案里。写题时要能说清楚"为什么跳过是安全的"，否则容易在去重和边界上出错。

有序数组两数之和（target = 9）：
  2   7   11   15
  L         R      2+15=17 > 9，右端偏大，R 左移
  2   7   11   15
  L     R          2+11=13 > 9，继续 R 左移
  2   7   11   15
  L   R            2+7=9 ✓ 命中

为什么敢直接丢掉 15？数组有序，2 是当前最小的数，连"最小 + 15"都超了，15 配谁都超——这一步排除的不是一个数，而是一整批候选，这就是对撞指针把 O(n²) 压到 O(n) 的原因。

快慢指针：一个探路，一个记账

两个指针同向而行，fast 负责探测，slow 负责记录"下一个待写入/待判断的位置"：

原地移除 val = 2：
fast:  [0] [1] [2] [3] [2] [4]   逐个判断"留不留"
slow:   0   1       2   3       只接收保留值，最终 slow = 4 就是新长度

三大经典应用——原地移除元素、链表找中点、链表判环——下一篇专门对比展开。

滑动窗口：连续区间的维护

把同向双指针中间的 [left, right] 看成一个窗口：right 扩张探索、left 收缩调整。适用信号是题目关心"连续"的子数组/子串，且窗口性质具有单调性（元素越多越容易满足、或越不满足条件）。它是同向双指针的推广，典型题如 209 长度最小的子数组：

求元素和 ≥ 7 的最短连续子数组：
[2 3 1 2 4 3]
 L      R         2+3+1+2=8 ≥ 7，先记录长度 4
    L  R          收缩：3+1+2=6 < 7，停，转而扩张 R
    L     R       3+1+2+4=10 ≥ 7，记录长度 3 ……

右指针负责"进"，左指针负责"出"，每一步都在维护窗口的合法性。两个指针各自最多走 n 步，整体 O(n)。

多指针：n 数之和的骨架

排序后固定一个（或两个）数，剩余范围用对撞指针搜索。固定层数每多一层，复杂度升一阶；去重和剪枝是主要工程量，详见本专题第 6 篇。

与其他专题的关系：复用思想，不重复展开

双指针题目分散在各主专题中，本专题的定位是"索引与提炼"，而不是重复讲解：

拿到新题时，可以用这个 checklist 判断该不该上双指针：

1. 能否通过移动指针 O(1) 地排除一批候选？（有序、对称、区间性质）
2. 是否要求原地完成、只用 O(1) 额外空间？（快慢指针的删除/压缩）
3. 关心的对象是否要求连续？（滑动窗口）
4. 暴力解是否是"两层枚举，且内层范围随外层单调收缩"？（对撞指针替代内层循环）

最小完整案例：977 有序数组的平方

用一道题把"对撞指针 + 不变量"走完整：非递减数组（可能含负数）中，返回每个数平方后仍有序的数组。

关键观察：平方后的最大值只会出现在两端（绝对值最大者在头或尾），所以从两端向中间对撞，每次把较大者放进结果数组的尾部：

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int left = 0, right = n - 1, pos = n - 1; // pos：结果数组的写入位置
        while (left <= right) {
            int l = nums[left] * nums[left];
            int r = nums[right] * nums[right];
            if (l > r) {
                res[pos--] = l;   // 左端平方更大，收走它
                left++;
            } else {
                res[pos--] = r;
                right--;
            }
        }
        return res;
    }
}

三要素齐了：指针含义（left/right 指向两端尚未处理的元素，pos 指向结果待写位置）、移动规则（谁的平方大谁被收走，对应指针内移）、终止条件（left > right，区间清空）。时间 O(n)，一个循环完成"先平方再排序"两步的活。

循环不变量：双指针写对的三步

任何双指针题，动手前先写完这三句话：

1. 含义：每个指针（或区间）代表什么？例如"slow 左边全部是已处理元素"。
2. 移动规则：什么条件下动谁？每次移动是否让区间严格缩小、不会死循环？
3. 终止条件：循环停下时，不变量能否直接给出答案？

三句话写不清楚，代码必然在边界上翻车；写清楚了，代码只是把定义翻译成循环。

专题题单

学习建议

• 每道题先写下两个指针的含义（fast 是什么、slow 是什么），再写移动条件和终止条件，最后才写代码。
• 对撞指针必答自查：移动指针跳过了哪些元素？为什么它们不可能属于答案？
• 快慢指针必答自查：循环结束时 slow 停在哪？它和新长度、中点、入环点的关系是什么？

参考

• 代码随想录 · 双指针法专题