← 回首頁

雙指標(Two Pointers)

想像一排「由矮到高排好隊」的人,你要找出兩個人、身高加起來剛好等於某個數。笨方法是每兩個人都湊一遍試試看,人多就慢得要命。聰明的做法是派兩個人分別站在最矮端最高端往中間夾:湊出來太矮就矮端往前一步、太高就高端往後一步。這就是雙指標(Two Pointers)——用兩根手指在同一份資料上分工移動、彼此配合,把「每一對都試」的慢工變成走一遍就搞定。下面你會看到對撞與快慢兩種指標玩法的實際動畫。

雙指標是用兩個索引在同一份資料上協同移動,取代 O(n²) 的雙層迴圈,把問題壓到 O(n)。依兩指標的相對運動方式,分成兩種典型用法:

1. 兩數之和(Two Sum)— 對撞指標

陣列需先排序遞增。left 指向最小值、right 指向最大值,比較 nums[left] + nums[right] 與 target: 和太小則 left++(換更大的數),和太大則 right--(換更小的數),和相等則命中;兩指標相遇仍未命中則無解。

陣列(逗號分隔,2–12 個非負整數,每個 0–99): target(0–999):
比較次數:0
藍色外框為 left/right 指標所在位置;找到配對時該兩格轉綠。

2. 移除元素(Remove Element)— 快慢指標

slow 從 0 開始、fast 逐格掃描全陣列:nums[fast] != val 時把它複製到 nums[slow] 並 slow++, 等於 val 則跳過(fast 前進、slow 不動)。全程就地覆寫,不配置額外陣列,掃描結束後 slow 即為新長度。

陣列(逗號分隔,2–12 個非負整數,每個 0–99): val(0–99):
寫入次數:0
綠色為已保留部分(0..slow);藍色外框為 slow/fast 指標所在位置。

3. 回文檢查(Palindrome Check)— 對撞指標

left/right 由兩端向中間逼近:先各自跳過非英數字元,再比較兩端字元(忽略大小寫), 不相符立即判定不是回文(提前結束,最佳情況 O(1));相符則向內縮,直到指標相遇。

字串(1–30 字,限 ASCII 可列印字元):
比較次數:0
暗淡格為被跳過的非英數字元;綠色格為已比對相符的字元;藍色外框為當前 left/right 指標。