模式：雙指標與滑動視窗

在有序陣列上的雙指標

[[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 和這些模式的同一根線。你現在有了一個真正的工具箱；下一級台階，講的是如何自信地揮舞它。