[algorithms] Two Pointers 雙指標 | 分享技術與生活

cover

雙指標的核心就一句話：用兩根指標把 O(n²) 降成 O(n)。聽起來很簡單，但知道什麼時候能用、怎麼移動指標，才是真功夫。

兩根指標省下一層迴圈

雙指標有三種：對撞指標（兩端往中間）、快慢指標（同向不同速）、滑動視窗（維護動態區間）。面試考雙指標的頻率極高，尤其是陣列和鏈表題，大概有三成可以用雙指標解。

對撞指標：從兩端夾擊

兩數之和（已排序），暴力 O(n²)，對撞指標 O(n)：

[2, 7, 11, 15]  target=9
 ↑          ↑
left       right
 
2 + 15 = 17 > 9 → right--
2 + 11 = 13 > 9 → right--
2 + 7 = 9 ✓

為什麼可以移動？因為陣列已排序。sum > target 時，right 往左才能變小；sum < target 時，left 往右才能變大。每次都在有效地排除不可能的組合。

int left = 0, right = nums.length - 1;
while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) return new int[]{left, right};
    if (sum < target) left++;
    else right--;
}

三數之和：固定一個，剩下兩個對撞

for (int i = 0; i < n - 2; i++) {
    if (i > 0 && nums[i] == nums[i-1]) continue; // 跳過重複
    int left = i + 1, right = n - 1;
    while (left < right) {
        // 對撞找 target = -nums[i]
    }
}

從 O(n³) 降到 O(n²)。面試經典中的經典。

盛水容器：關鍵是移動較矮的那根

一排高度不一的柱子，任選兩根當容器的兩壁，能裝多少水由「較矮那根 × 兩根間距」決定。暴力枚舉每一對是 O(n²)，對撞指標一趟 O(n)。

int maxArea(int[] height) {
    int left = 0, right = height.length - 1, max = 0;
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        max = Math.max(max, area);
        if (height[left] < height[right]) left++;
        else right--;
    }
    return max;
}

為什麼永遠移動較矮的那根？面積被矮的一邊卡住，移動高的那根只會讓寬度變小、天花板還是那個矮的，穩虧；只有把矮的換掉才有翻盤機會。移錯邊，你就跟正解擦身而過。

回文判斷

while (left < right) {
    if (s.charAt(left) != s.charAt(right)) return false;
    left++;
    right--;
}

對撞指標的最簡單應用。

快慢指標：同向不同速

陣列版：移除元素

slow 指向「下一個要放的位置」，fast 負責掃描：

int slow = 0;
for (int fast = 0; fast < n; fast++) {
    if (nums[fast] != val) {
        nums[slow++] = nums[fast];
    }
}
return slow; // 新長度

移除重複、移動零、都是同一個模式。fast 找有效元素，slow 負責收集。

鏈表版：檢測環

快指標一次走兩步，慢指標一次走一步。有環的話，快的遲早追上慢的。

ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true;
}
return false;

為什麼一定會相遇？因為快指標每步比慢指標多走一格，所以每一步「距離差」都縮小 1。想像你在操場跑步，跑得快的人終究會追上跑得慢的人。

找環入口：相遇後，一根指標回到 head，兩根都改成一步一步走，再次相遇就是入口。數學證明要用到 Floyd’s Cycle Detection，這裡就不展開了——面試記結論就行。

找鏈表中點

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
return slow;

找倒數第 k 個

fast 先走 k 步，然後 fast 和 slow 一起走。fast 到底的時候 slow 就在倒數第 k 個。

for (int i = 0; i < k; i++) fast = fast.next;
while (fast != null) {
    slow = slow.next;
    fast = fast.next;
}
return slow;

什麼時候用雙指標？

問自己：

陣列/字串已排序嗎？→ 對撞指標
需要 in-place 操作嗎？→ 快慢指標
鏈表有環/找中點/找倒數？→ 快慢指標
連續子陣列/子字串？→ 滑動視窗

雙指標的好處是空間 O(1)。很多題目用 Hash Map 也能解，但面試官追問「能不能不用額外空間」的時候，雙指標就是你的答案。

🎬 互動視覺化：三種雙指標動畫 — 對撞、快慢、滑動視窗並排跑，看兩根指標怎麼移動、什麼條件下該收哪一根。

雙指標技巧就像筷子：兩根棍子單獨沒用，但配合好了什麼都能夾。關鍵是知道什麼時候該動哪一根。

接下來往哪走

Sliding Window 滑動視窗 — 下一篇：雙指標的第三種形態，連續區間題的專章深入
Linked List 鏈結串列 — 快慢指標抓環、找中點的主場，先熟結構再回頭看技巧

Terry Yao's Blog

目錄

Two Pointers 雙指標