模式：双指针与滑动窗口

在有序数组上的双指针

[[two-pointers|双指针]]模式在一个数组上保留两个下标，并根据它们所发现的东西，让它们相向移动（或同向并进）。经典用法：给定一个*有序*数组，找出和为目标值的一对数。暴力解检查每一对——O(n²)。双指针利用有序性，在 O(n) 内做到。

Sorted:  [ 1   3   4   6   8   9 ]      target = 10
           L                   R
  1 + 9 = 10  -> found!  (too small? move L right; too big? move R left)

  e.g. target = 11:
           L               R          1 + 8 = 9  < 11  -> L++
               L           R          3 + 8 = 11 -> found!

L 从最左起，R 从最右起。和太小，唯一变大的办法是 L++；太大，唯一变小的办法是 R--。每一步都排除一种可能。

#include <vector>

bool hasPairSum(const std::vector<int>& a, int target) {
    int L = 0, R = (int)a.size() - 1;
    while (L < R) {
        int sum = a[L] + a[R];
        if (sum == target) return true;
        else if (sum < target) L++;   // need a bigger sum
        else R--;                     // need a smaller sum
    }
    return false;
}

一个 while 循环，两个指针相向逼近。数组是有序的，所以每次比较都排除一整行的配对。O(n) 时间，O(1) 额外空间。

快慢指针

第二种风味，是让两个指针沿同一序列以*不同速度*移动。让一个慢指针每次走一步，一个快指针每次走两步。如果结构绕回了自身，快的那个最终会套圈追上慢的，两者相遇——这正是检测链表中环的那个著名办法，不用任何额外内存。

struct Node { int val; Node* next; };

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next;          // +1 step
        fast = fast->next->next;    // +2 steps
        if (slow == fast) return true;   // they met: there's a cycle
    }
    return false;                   // fast reached the end: no cycle
}

若有环，+2 的指针会不断追近 +1 的指针，直到把它套圈。若无环，快指针就直接跑到尽头。O(n) 时间，O(1) 空间。

滑动窗口

当一个问题问到连续的子数组或子串时——「最长的无重复连续段」「任意连续 5 个的最大和」——[[sliding-window|滑动窗口]]模式就大放异彩。设想一个窗口框住数组的一段。你不去从头重算每个窗口，而是*滑动*它：在右边加入新元素，在左边丢掉旧元素，并更新一个滚动的累计值。每个元素进出窗口各一次，所以整趟扫描是 O(n)，而非 O(n²)。

Array: [ 2  1  5  1  3  2 ]   find max sum of any 3 in a row (window k=3)

  [2  1  5] 1  3  2     sum = 8
   2 [1  5  1] 3  2     slide: -2 +1  -> 8 - 2 + 1 = 7
   2  1 [5  1  3] 2     slide: -1 +3  -> 7 - 1 + 3 = 9   <- best
   2  1  5 [1  3  2]    slide: -5 +2  -> 9 - 5 + 2 = 6
                                          answer = 9

每一次滑动是一次减法 + 一次加法——O(1) 的工作量——而不是把 k 个元素重新求和。窗口在单趟里滑过整个数组。

#include <vector>

int maxSumWindow(const std::vector<int>& a, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += a[i];   // first window
    int best = sum;
    for (int i = k; i < (int)a.size(); i++) {
        sum += a[i] - a[i - k];     // slide: add right, drop left
        best = std::max(best, sum);
    }
    return best;
}

固定大小的窗口：第一个窗口算一次，之后每步都是 + 新的 - 旧的。总工作量 O(n)。

可变窗口，以及如何认出这个模式

许多窗口并非固定大小——它们会*伸缩*。要找最长的无重复字符子串，你把窗口的右边界向外扩去纳入新字符，而每当出现重复，你就收缩左边界，直到那个重复消失。两个边界都只会*向右*移动，所以即便有两个移动的指针，每个也至多到访每个位置一次——整体仍是 O(n)。

留意这些模式和这一级台阶其余内容的共通之处：它们都用一种更聪明、会*复用*已知信息的扫描——滚动累计值、有序的次序、已访问集合——来取代盲目的、反复的重算。这个本能——「别去重做我已经做过的活」——是贯穿贪心、DP 和这些模式的同一根线。你现在有了一个真正的工具箱；下一级台阶，讲的是如何自信地挥舞它。