算法设计范式
双指针
双指针技巧用两个下标以协调一致的方式在序列中移动，从而把「朴素做法要靠嵌套循环」的工作压缩成单趟扫描。你不是去比较每一对位置，而是保留两个标记，并依据所见来推进其中之一——这就把许多 O(n^2) 的问题变成了 O(n)。它是数组与字符串上最稳定好用的套路之一，并且很依赖数据已排序（或别的方式单调），因为正是这种有序性告诉你该动哪个指针。
常见有两种形态。对撞指针从两端出发、相向而行：要判断一个有序数组里是否有两个数之和等于目标，就把一个指针放在头、一个放在尾，每一步比较它们的和与目标——太小，就把左指针往右推以增大和；太大，就把右指针往左收以减小和；相等，就找到了这一对。由于每一步都让某个指针向内移、且它们不会再越回去，整趟扫描就是 O(n)。同样的思路也能原地反转数组、或检验回文。
另一种形态是同向、以不同速度行进的独立（常称快慢）指针：一个慢指针标记「下一个要保留的元素该放哪」，一个快指针在前面扫描，这是从有序数组里去重、或原地过滤的经典写法。在链表里，一个每走两步、另一个每走一步的指针能检测出环（Floyd 的龟兔赛跑）、并找到中间节点。统一的思想是：两个指针合在一起编码了一个你能巧妙推进的状态——绝不重看单趟扫描已经处理过的部分——从而给出 O(n) 的时间和 O(1) 的额外空间。
bool hasPair(const vector<int>& a, int target) {
int lo = 0, hi = a.size() - 1; // sorted input required
while (lo < hi) {
int s = a[lo] + a[hi];
if (s == target) return true;
if (s < target) ++lo; // too small: grow the sum
else --hi; // too large: shrink the sum
}
return false; // O(n) time, O(1) space
}每一步恰好让一个指针向内移，所以在有序输入上扫描是 O(n)。
双指针通常依赖输入已排序——正是这种有序性告诉你下一步该动哪个指针。在未排序的数据上，你可能得先排序（额外 O(n log n)），或改用哈希表。滑动窗口正是它的近亲：一个由左右两个指针界定的窗口。
又称
另见