用兩個指標一起掃,把 O(n²) 的暴力搜尋壓到 O(n)。頭尾夾、快慢追,都是它。
頭尾對撞(opposite ends) —— left 從 0、right 從尾,往中間夾。用在:排序陣列找兩數和、判斷回文、反轉、盛水最多的容器。
快慢指標(fast & slow) —— 兩個同方向,一次走一步 vs 兩步。用在:偵測環(龜兔)、找鏈結串列中點、原地去重。
讀寫同向 —— 一個「讀」一個「寫」,原地整理資料(這就接到下一頁的滑動視窗)。
共同點 —— 兩個指標的移動有規律,合起來只掃一遍 → O(n)。
暴力法 —— 雙層迴圈試「所有配對」,O(n²)。
雙指標 —— 利用「已排序」或「單調」的性質,每次比較就能確定該移哪個指標,一次淘汰一整排不用試的。
例如排序陣列找兩數和 —— 和太大就移右指標(讓總和變小)、太小就移左(變大),絕不回頭。
兩個指標各自最多走 n 步 —— 合計 O(n)。
O(n log n))往往仍比 O(n²) 划算。兩個人從書架兩頭往中間找,比一個人從頭翻到尾快一倍。
一快一慢跑同一圈,只要快的追上慢的,就代表這條路有環。
一手讀原始資料、一手寫整理後的結果,原地完成、不另開空間。
在排序好的陣列裡找「兩數和 = 10」。左指標 L 從最小、右指標 R 從最大:和太大就 R 左移(變小)、和太小就 L 右移(變大),往中間夾。淡掉的是已排除、不用再看的。按「下一步」。
從排序兩數和、回文、反轉、盛水容器、三數之和,到快慢指標偵測環 / 找中點、讀寫去重、移動零、合併。
❌ 頭尾夾用在沒排序的資料 —— 「太大移右、太小移左」需要單調性,沒排序會錯。
❌ while 條件寫錯 —— 頭尾夾是 left < right(不能 <=,否則自己跟自己配),邊界差一格很常見。
❌ 忘了跳過重複 —— 3sum 這種要去重,不然會冒出重複答案。
❌ 快慢指標沒檢查 fast.next —— 快指標一次走兩步,要先確認 fast 和 fast.next 都在,否則 None.next 爆掉。
[1,3,4,6,8,11,15] 找和為 10 的兩數,L、R 怎麼移動?最後停在哪兩個數?O(n)?它需要什麼前提?把答案打到對話裡,我幫你對。