[L1] 双指针的两种形式：对撞指针与快慢指针

一句话结论

双指针分对撞（两端向中间收缩）和快慢（同向不同速）两类，将 O(n²) 暴力枚举降至 O(n)。

体系讲解

什么是双指针

双指针是在数组或序列上维护两个游标，通过游标的协同移动在单次遍历内完成原本需要嵌套循环的工作，核心收益是将时间复杂度从 O(n²) 降到 O(n)，且通常不需要额外空间（O(1)）。

对撞指针（Two-pointer / Opposite Direction）

两个指针分别从序列首尾出发，依据条件向中间收缩，直到相遇或交叉为止。

适用前提：序列有序，或问题具有"两端夹逼"特性。

初始：[←left                right→]
条件不满足时：移动其中一端，缩小搜索空间
终止：left >= right

典型题型：有序数组两数之和、字符串回文判断、盛最多水的容器。

快慢指针（Fast-Slow Pointer）

两个指针从同一起点出发，但步速不同（fast 每次走 2 步，slow 走 1 步；或 fast 超前 k 步）。

适用前提：序列中存在周期/循环，或需要在不知总长度的前提下定位特定位置。

初始：fast = slow = head
每轮：slow += 1，fast += 2
交汇：说明存在环；若 fast 先到末尾，则无环

典型题型：链表环检测（Floyd）、链表中点、删除倒数第 N 个节点。

选型速查

场景	选哪种	前提条件
有序数组找两数之和	对撞指针	数组有序
回文判断	对撞指针	无需排序
原地移除/去重元素	快慢指针	无需排序
链表环检测	快慢指针	链表结构
链表中间节点	快慢指针	链表结构

考察意图

考查候选人是否理解双指针的本质——利用问题的单调性/周期性消除冗余枚举，而非死记硬背模板。能区分两种形式并说出各自前提条件，说明对数组算法有系统性认知。

追问链

1. 对撞指针为什么要求数组有序？
   简答：有序保证了"左指针右移 → 和增大，右指针左移 → 和减小"的单调性。若无序，移动任意一端后结果不可预测，无法收缩搜索空间。

2. 快慢指针如何确认链表有环？为什么快指针走 2 步而不是 3 步？
   简答：若有环，fast 和 slow 最终一定在环内相遇（fast 每轮追近 1 步，必然追上）。走 3 步也能检测环，但计算入环点的数学推导更复杂；走 2 步是最简且推导最简洁的选择。

3. 双指针能用于无序数组吗？
   简答：快慢指针可以（原地覆盖场景不依赖顺序）；对撞指针通常不行，除非问题本身有其他收缩依据（如"任意两端取较小值"的容积问题）。

4. 从 O(n²) 降到 O(n) 的关键前提是什么？
   简答：每次指针移动后，当前状态不会再被"更优解"考虑，即移动具有单调剪枝效果。缺乏这个前提时双指针不适用，暴力枚举反而更安全。

易错点

1. 对撞指针忘记有序前提：直接套用对撞指针解无序数组，会漏掉合法解。需先确认数组有序，或先排序（O(n log n) 代价）。
2. 快慢指针步长写错：快指针每次移动 2 步写成 $fast = $fast->next->next，但未判断 $fast->next 是否为 null，导致空指针异常。务必在移动前判断。
3. 终止条件混淆：对撞指针的终止条件是 $left < $right（严格小于），写成 <= 会导致元素与自身比较，产生错误结果。

代码示例

<?php

// ── 对撞指针：有序数组中找两数之和等于 target ──────────────────
function twoSumSorted(array $nums, int $target): array
{
    $left = 0;
    $right = count($nums) - 1;

    while ($left < $right) {
        $sum = $nums[$left] + $nums[$right];
        if ($sum === $target) return [$left, $right];
        $sum < $target ? $left++ : $right--;
    }

    return [];
}

// ── 快慢指针：找数组中间位置（模拟链表中点思路） ─────────────────
function middleIndex(array $nums): int
{
    $slow = 0;
    $fast = 0;
    $n    = count($nums);

    while ($fast < $n && $fast + 1 < $n) {
        $slow++;
        $fast += 2;
    }

    return $slow; // 奇数长度取正中，偶数长度取右中
}