雙指標與滑動視窗 Two pointers and sliding windows · 演算法 Algorithms

雙指標與滑動視窗

兩個索引一起往前走，每一步都排除掉不可能的答案：把原本要兩層迴圈的問題變成走一遍就好。

問題

目標

1/15

6
0lo
8
1
10
2
11
3
13
4
17
5
18
6
24
7
28
8
33
9
38
10
41
11
46
12
52
13
56
14
61
15hi

正在相加的兩個已經排除答案

雙指標：看了幾組

全部跑完

暴力雙層迴圈

排好序的數字，目標 57。lo 從最小的開始，hi 從最大的開始。

亮起來的是這一步執行的程式碼

1function pairWithSum(a: number[], target: number): [number, number] | null {
2  let lo = 0, hi = a.length - 1;
3  while (lo < hi) {
4    const sum = a[lo] + a[hi];
5    if (sum === target) return [lo, hi];
6    if (sum < target) lo++;
7    else hi--;
8  }
9  return null;
10}
11 
12function longestUnique(text: string): [number, number] {
13  const s = Array.from(text);
14  const last = new Map<string, number>();
15  let left = 0, bestStart = 0, bestLen = 0;
16  for (let right = 0; right < s.length; right++) {
17    const seen = last.get(s[right]);
18    if (seen !== undefined && seen >= left) {
19      left = seen + 1;
20    }
21    last.set(s[right], right);
22    if (right - left + 1 > bestLen) {
23      bestStart = left;
24      bestLen = right - left + 1;
25    }
26  }
27  return [bestStart, bestLen];
28}

模型假設與範圍

Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

什麼時候用

資料已經排好序，要找一組滿足條件的配對（兩數和、三數和、最接近的一對）：兩端往中間夾。
要找「最長／最短的連續一段」滿足某個條件：右邊一直擴張、條件被破壞時左邊收縮。
原地處理陣列（去重、把零移到最後、合併兩個排好序的陣列）：一個指標讀、一個指標寫。

和其他主題的關係

被這些用到: 考題：Two Sum 考題：串列有沒有環考題：接雨水系統設計 · 搜尋索引
延伸閱讀: 二分搜尋排序

時間與空間複雜度（Big O）

操作	平均	最差
兩數和（雙指標）前提是陣列已經排好序	O(n)	O(n)
兩數和（暴力）	O(n²)	O(n²)
最長不重複子字串（滑動視窗） right 和 left 都只會往前走，各走最多 n 步	O(n)	O(n)
最長不重複子字串（暴力） σ 是字元種類數	O(n·σ)	O(n²)

空間：O(1) – O(σ)，兩數和只要兩個索引；滑動視窗要記每個字元上次出現的位置

Big O 實測：n 變大時步數怎麼長

數的是：檢查了幾組，或指標移動幾次

	Big O	n = 250	n = 500	n = 1,000	n = 2,000	成長倍數：實測（理論）
兩數和：雙指標（找不到）	O(n)	249	499	999	1,999	×8.0 (×8.0)
兩數和：暴力（找不到）	O(n²)	31,125	124,750	499,500	1,999,000	×64 (×64)
最長不重複子字串：滑動視窗	O(n)	307	613	1,238	2,468	×8.0 (×8.0)

和其他做法比

	雙指標／滑動視窗	暴力雙層迴圈
兩數和：找不到（最差）	999	499,500
兩數和：找得到	25	5,960
最長不重複：26 種字母	1,217	7,334
最長不重複：100 種字元	1,124	14,732

n = 1,000。兩數和看的是「檢查了幾組」，最長子字串看的是「指標移動」對上「暴力法看了幾個字元」。暴力法找最長子字串時，每個起點最多只能走到字母種類數加一就一定會重複，所以它的成本是 n 乘上字元種類數：字元種類越多，差距越大。

真實世界裡的它

合併排序的合併步驟，就是兩個指標各走一個已排序的半邊。
網路監控的「過去 60 秒流量」、限流器的滑動視窗，都是時間軸上的滑動視窗。
搜尋引擎把兩個詞的文件清單取交集，就是兩個指標各走一串排好序的文件編號。

取捨與陷阱

兩數和的夾擠法只在排好序時成立；沒排序要先花 O(n log n) 排序，或改用雜湊表 O(n)。
滑動視窗要求條件是「單調」的：窗口變大只會更難滿足、變小只會更容易。不是這樣的條件（例如和剛好等於 k、但有負數）就不能這樣縮。
邊界最容易錯：lo < hi 還是 lo ≤ hi、窗口長度是 right − left 還是 right − left + 1。

演算法