30 核心算法 第04集 - 双指针技巧

Source: Dev.to

为什么双指针技巧实际上是关于协同

双指针技巧常被当作一种技巧来教授。

• 将一个指针从左侧移动。
• 将另一个指针从右侧移动。
• 在中间的某处相遇。

它有效，所以人们很容易把它当作一种需要记住的模式。
这种看法忽略了该技巧实际在做什么。

双指针并不是为了更快地扫描数组。
它是关于在共享约束下协调移动。

单独移动的代价

想象一下，在一个大型有序结构中搜索某个条件。

一种方法是从一侧一步一步移动，检查所有内容。这种方式直接且可靠，但它忽略了一件重要的事：结构本身已经告诉你哪些地方不需要查找。

使用单一指针移动会浪费这些信息。每一步仅反映局部决策，且与其他位置的情况脱节。虽然在前进，但进展缓慢。

双指针：通过对齐推进

一旦引入第二个指针，问题就会改变。

现在每一次移动都是相对的。一个指针的前进取决于另一个指针的视角。决策是成对进行的，而不是孤立的。

不再问：

“我接下来应该做什么？”

系统会问：

“这两个位置应该如何一起移动？”

这种协同能够快速压缩可能性，无需额外的内存或复杂的逻辑。

为什么顺序如此重要

双指针只有在移动有意义时才有效：

• 已排序的数组
• 单调序列
• 结构化边界

没有顺序，指针的移动就变成了猜测。有了顺序，每一步都能排除整类状态。这就是为什么在合适的情境下，这种技巧几乎显得神奇——而在不合适的情境下则完全无用。其威力并非来源于指针本身，而是数据所提供的保证。

双指针作为约束求解器

许多双指针问题并不真正是关于搜索的。它们是关于维护不变式的：

• 必须保持在界限内的和
• 必须满足条件的窗口
• 必须不超过限制的距离

指针的移动不是为了探索，而是为了重新平衡。当一侧违反约束时，另一侧会进行补偿。算法不断将系统轻推回有效状态。这个反馈循环才是真正的机制。

滑动窗口是一场对话

滑动窗口技术常常与双指针一起归类，原因在此。

• 左指针收紧约束。
• 右指针放宽约束。

单独的移动没有意义。它们一起形成了一场对话——在重要条件周围扩张、收缩并保持稳定。这是最纯粹的协作形式。

当双指针失效时

双指针假设合作。数据在指针移动时必须能够可预测地响应。如果结构不单调变化，协同就会失败。这就是该技巧在以下情况下会遇到困难的原因：

• 未排序的数据
• 非单调条件
• 需要全局上下文的问题

当局部移动不能可靠地改善或恶化条件时，指针移动就失去了信号。该技巧并非脆弱——它诚实地展示了自己的局限性。

The Trade‑off It Makes Explicit

Two Pointers 通过牺牲通用性来优化空间和时间。它不会遍历所有情况、回溯或从错误假设中恢复。但只要约束成立，它就能以最小的努力、几乎没有额外开销得到答案。这是一种有意的权衡。

要点

双指针技术并不是捷径。它是一种通过确保移动永不独立来取得进展的方法。每一步都受到另一方的启发，每一个决定都要在约束条件下平衡。

这种思想远远超出数组的范畴——在任何系统需要协同移动以保持在界限内的地方都能看到。正因为如此，双指针仍然是一项核心技术，而不是巧妙的技巧。