比較次數:0
藍色外框為 left/right 指標所在位置;找到配對時該兩格轉綠。
想像一排「由矮到高排好隊」的人,你要找出兩個人、身高加起來剛好等於某個數。笨方法是每兩個人都湊一遍試試看,人多就慢得要命。聰明的做法是派兩個人分別站在最矮端和最高端往中間夾:湊出來太矮就矮端往前一步、太高就高端往後一步。這就是雙指標(Two Pointers)——用兩根手指在同一份資料上分工移動、彼此配合,把「每一對都試」的慢工變成走一遍就搞定。下面你會看到對撞與快慢兩種指標玩法的實際動畫。
雙指標是用兩個索引在同一份資料上協同移動,取代 O(n²) 的雙層迴圈,把問題壓到 O(n)。依兩指標的相對運動方式,分成兩種典型用法:
陣列需先排序遞增。left 指向最小值、right 指向最大值,比較 nums[left] + nums[right] 與 target:
和太小則 left++(換更大的數),和太大則 right--(換更小的數),和相等則命中;兩指標相遇仍未命中則無解。
slow 從 0 開始、fast 逐格掃描全陣列:nums[fast] != val 時把它複製到 nums[slow] 並 slow++,
等於 val 則跳過(fast 前進、slow 不動)。全程就地覆寫,不配置額外陣列,掃描結束後 slow 即為新長度。
left/right 由兩端向中間逼近:先各自跳過非英數字元,再比較兩端字元(忽略大小寫), 不相符立即判定不是回文(提前結束,最佳情況 O(1));相符則向內縮,直到指標相遇。