双指针 · Two Pointer

很多数组 / 链表问题,暴力写法都要嵌套两层循环 O(n²);但只要数据本身带有某种顺序, 就能用两个指针分工协作、各自单向扫描,把整个过程压成一趟 O(n),空间常常还是 O(1)。 双指针不是单个算法,而是一类方法。按两指针的相对运动可分为三大流派:

异构指针(同向追赶):两指针一前一后朝同一方向走,各负责一类元素——慢指针标记「下一个写入位置」, 快指针在前面扫描。左右对撞:一个指针从最左、一个从最右,每步按条件让其中一个往中间移动, 在 left < right 内收缩——二分查找、接雨水都属于这一类。快慢指针:主要用于链表—— 一个每次走一步、一个走两步,用「速度差」换来「感知前方 / 后方」的能力(Floyd 判环)。

每页都可修改输入、单步推进,观察两个指针(青色 = 主指针 / 橙色 = 副指针)在数组 / 链表上移动,旁边代码逐行点亮。 同向双指针在「连续子数组 / 子串」问题上的系统展开,见相邻的 滑动窗口 Sliding Window 系列。

异构指针:同向追赶,各扫一类 Move Zeroes · 快慢同向

移动零：把 0 全部移到末尾

只许交换且要保持非零元素相对顺序。慢指针标记写入位置、快指针向前扫描，两者拉开「已就位」与「待处理」的分界。

Merge Sorted Array · 逆向

合并两个有序数组：从后往前填，避免覆盖

把一个有序数组原地并进另一个的尾部空位。从前往后填会覆盖未读的数，改成从后往前填即可避免。

Sparse Vector · 归并对齐

稀疏向量点积：两个有序列表对齐求交

超大稀疏向量只存非零项。两个列表都按下标有序，求点积正是双指针归并：谁的下标小谁前进，相等才乘进结果。

左右对撞:从两端往中间夹 Binary Search · 折半收缩

二分查找：左右指针不断折半

最基础的对撞指针：左右边界圈住搜索区间，每轮看中点并把区间减半。附 mid 计算的整型溢出陷阱。

Trapping Rain Water · 对撞

接雨水：不看整体，只看每根柱子

难点在建模：不去找有几个坑，而问每个位置头顶能积多高水。三种解法并排，双指针那种只需 $O(1)$ 空间。

快慢指针:链表里的速度差 Fast & Slow · Floyd

快慢指针：一步 vs 两步，找出环和中点

让 fast 每次走两步、slow 走一步，速度差换来对链表全局结构的感知：判圈、找环入口、定位中点与倒数第 $k$ 个。

落地:生产代码中的双指针 applications · 真实应用

应用实例：生产代码中的双指针

归并排序的合并步、std::remove 的保留压实、GC 的标记整理、环形缓冲的读写偏移——这些生产代码的内核都是三种指针思路的变体。