双指针 · Two Pointer
很多数组 / 链表问题,暴力写法都要嵌套两层循环 O(n²);但只要数据本身带有某种顺序, 就能用两个指针分工协作、各自单向扫描,把整个过程压成一趟 O(n),空间常常还是 O(1)。 双指针不是单个算法,而是一类方法。按两指针的相对运动可分为三大流派:
异构指针(同向追赶):两指针一前一后朝同一方向走,各负责一类元素——慢指针标记「下一个写入位置」, 快指针在前面扫描。左右对撞:一个指针从最左、一个从最右,每步按条件让其中一个往中间移动, 在 left < right 内收缩——二分查找、接雨水都属于这一类。快慢指针:主要用于链表—— 一个每次走一步、一个走两步,用「速度差」换来「感知前方 / 后方」的能力(Floyd 判环)。
每页都可修改输入、单步推进,观察两个指针(青色 = 主指针 / 橙色 = 副指针)在数组 / 链表上移动,旁边代码逐行点亮。 同向双指针在「连续子数组 / 子串」问题上的系统展开,见相邻的 滑动窗口 Sliding Window 系列。
移动零：把 0 全部移到末尾
LeetCode 283。只许交换、还要保持非零元素相对顺序——典型的异构指针：慢指针 j 标记「下一个非零元素的写入位置」，快指针 i 向前扫描，每遇到一个非零就和 j 交换、j 前进一格。单步观察两指针拉开的「已就位 ↔ 待处理」分界，页末还会说明它与 cyclic sort 的关系。
合并两个有序数组：从后往前填，避免覆盖
LeetCode 88。要把 nums2 原地并进 nums1 的尾部空位。从前往后填会覆盖掉尚未比较的数；改成从后往前填，每次把两端末尾更大的那个放进最末空位，被覆盖的位置一定已经读取过。单步观察三个指针 p1 / p2 / p 一起后退。
稀疏向量点积：两个有序列表对齐求交
常见面试题。元素几乎全是 0 的超大向量，只存非零项 (index, value)。求点积要找两边 index 都非零的位置相乘——两个列表都按 index 有序，正是双指针归并：谁的 index 小谁前进，相等才乘进结果。和「合并有序链表」同一手法，follow-up 还讨论一边特别短时如何处理。
二分查找：左右指针不断折半
最基础的对撞指针。在有序数组里找一个数：left / right 圈住搜索区间，每次看正中间 mid——a[mid] 偏大就把 right 收到 mid 左边、偏小就把 left 推到 mid 右边，区间每轮减半，O(log n) 内命中。单步观察区间如何收缩，并说明 mid = (left+right)/2 的整型溢出陷阱。
接雨水：不看整体，只看每根柱子
LeetCode 42。柱状图能接多少雨水？难点在建模——不去找「有几个坑」，而是问每个位置头顶能积多高水 = min（左边最高，右边最高）- 自己。三种解法并排：DP 预存左右最大值、单调栈，以及双指针——left / right 对撞，谁那侧的「已知最高」更矮就结算谁，O(1) 空间边走边算。
快慢指针：一步 vs 两步，找出环和中点
链表的局限在于每个节点只能看到 next。让 fast 每次走两步、slow 走一步，速度差换来对全局结构的感知：有环则两指针必在环内相遇（Floyd 判圈）；相遇后一个回到表头同速再走，重逢点正是环的入口; fast 到尾时 slow 恰在中点；让 fast 先走 k 步则 slow 落在倒数第 k 个。一页演示四种用法。
应用实例：生产代码中的双指针
merge sort 的合并步、std::remove / Java Arrays 的「擦除-填充」、GC 的标记-整理(compaction)、读写两个 offset 的环形缓冲、滑动窗口限流、归并多路有序流（LSM / 数据库 merge join）——这些生产代码的内核，都是本系列三种指针思路的变体。每个例子都回答同一个问题：哪两个指针、各管什么。