演算法設計範式
雙指標
雙指標技巧用兩個索引以協調一致的方式在序列中移動，從而把「樸素做法要靠巢狀迴圈」的工作壓縮成單趟掃描。你不是去比較每一對位置，而是保留兩個標記，並依據所見來推進其中之一——這就把許多 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)），或改用雜湊表。滑動視窗正是它的近親：一個由左右兩個指標界定的視窗。
又稱
另見