雙指針 Two Pointers

LeetCode 解題系列

14 min readMar 31, 2025

對於不是很愛刷扣的我來說，雙指針 (Two Pointers) 是我最愛的題型之一，他適合用在陣列、字串及 Linked List 上，最簡單的定義就是透過兩個「指針」指向不同位置，同時（非同時）移動並逐漸縮小搜尋範圍，通常可以達成時間跟空間複雜度優化的效果，真的算是簡單易懂、效果又好的一種技巧。

指針：大家也別把指針這兩個字想得太難，說穿了就是記住兩個位置而已，再繼續往下看，就可以知道了。

LeetCode 雙指針的練習題: https://leetcode.com/problem-list/two-pointers/

雙指針的類型

雙指針又可以分為幾種不同的類型，但整理起來要注意地方就三個，大家可以透過後面列出來練習題目感受看看。

指針移動的「方向」
指針移動的「條件」
「停止移動」的條件

左右指針

左右指針顧名思義就是兩個指針分別從頭跟尾開始（大部分情況），朝反方向前進。

這樣解釋太抽樣了，直接來看相關題目：

LeetCode 344. Reverse String
題目: 要求寫一個函式，要將一個字串做 reverse，例如輸入是 abc，輸出就要是 cba。
輸入是字元陣列，例如 [‘a’, ‘b’, ‘c’]
輸出是 reverse 的結果，例如 [‘c’, ‘b’, ‘a’]
特殊要求: 要求要 in-place，空間複雜度為 O(1) → 也就是不能用額外的空間，必須要在原本的陣列裡操作。

如果不管特殊要求，其實最簡單的做法就是建立一個跟輸入一樣大的陣列，掃描原陣列，但反向填入新陣列，最後回傳這個新的陣列即可，但這樣就違反了特殊要求了。

分析一下題目，reverse 就是把第一個字元放到最後、把最後一個字元放到第一個，也就是第一個字元跟最後一個交換、第二個字元跟倒數第二個交換，依序類推。這時候就很適合用左右指針了，記得，指針就只是記憶位置而已。

建立左右指針，左指針指向第一個位置、右指針指向陣列尾端。
左指針指向的值與右指針指向的值交換。
交換完成後，左指針往右走一格、右指針往左走一格。
重複 1 ~ 3，直到符合停止條件: 左指針 ≥ 右指針，也就是兩個指針交會了。

用 JS 實作起來就是這樣，是不是簡單又有趣～

var reverseString = function(s) {
    // left 左指針，從 0 開始
    // right 右指針，從陣列尾端開始
    let left = 0, right = s.length- 1;
    // 左右指針還沒相撞，繼續執行
    while(left < right) {
        // 交換左右指針指向的值
        [s[left], s[right]] = [s[right], s[left]];
        // 左指針往右走
        left++;
        // 右指針往左走
        right--;
    }
};

備註: 這類的 in-place memory 的題目，蠻多都不需要回傳值，LeetCode 會去檢查輸入的那個陣列，有的時候會要求回傳陣列的某個 index，要注意題目的要求。

以這題而言，認真分析起來就是:

指針移動的「方向」：左指針往右走、右指針往左走。
指針移動的「條件」：沒有什麼特殊的限制，交換完了就可以移動了。
「停止移動」的條件：當左右指針交會時，表示整個陣列都已經掃描過一次了，就可以結束了。

類似題目:

可以試試看上述三題，寫完後應該可以發現，整個程式碼的「樣子」會長得很像 344. Reverse String 這題，就是中間需要多注意一些判斷而已，也可以試試看分析指針移動的條件與方向、停止移動的條件等。

同向指針

經過前文的左右指針，相信大家看到這個「同向」指針應該能猜到，這種類型的指針移動的方向是一致的、同方向的。不過，有的時候這兩個指針可能是指向兩個不同的陣列、字串或是 Linked List（雙向指針也會這種題型喔）。

一樣，讓我們直接來看題目吧：283. Move Zeroes

題目: 要求寫一個函式，將輸入陣列中的 0 都移到陣列尾端，且要維持非零數字原本的相對排序順序。
輸入是一個整數陣列，例如 [0, 1, 0, 3, 12]
輸出的結果會是 [1, 3, 12, 0, 0] → 把 0 都移到尾端，且 1, 3, 12 維持原本的順序。
特殊要求: 同樣要求是 in-place，不能使用額外的空間（也就是不能多複製一個陣列出來）。

在不管特殊要求的情況下，我們會怎麼做呢？大概是建立一個新陣列，掃描輸入的陣列，遇到非零的數字就 push 進新陣列中，最後回傳新陣列即可。但這樣就太簡單啦，在需要符合特殊條件下，我們可以怎麼做呢？

仔細想一下，我們要把 0 移到陣列尾端，這個意思反過來就是「把非零數字往前移」，既然要把 0 往尾端移、又要把非零數字往前移，那就讓他們交換就好？我們來想辦法記住目前陣列中掃描到的、最後一個 0 的位置，另外一個指針則開始往右掃描，只要第二個指針掃描到不是 0 的數字，就跟第一個指針交換。也就是：

指針 1: 紀錄最靠近開頭的、數字是 0 的 index
指針 2: 往右掃描到第一個非 0 數字

指針 1 先指向 index 0，指針 2 也從 index 0 出發
指針 2 往右掃描，直到遇到第一個非 0 數字
指針 1 跟指針 2 交換
指針 1 往右走一格 → 這邊蠻關鍵的，由於指針 2 是往右掃描遇到的第一個非 0 數字，那指針 1 往右走，應該就還是最靠近開頭的、數字是 0 的 index，不是也沒關係，等一下看後續分析。
指針 2 走到陣列尾端，全部掃描完畢就停止。

以 LeetCode 提供的範例而言，我們畫個圖看看：

左圖是最一開始的情況，指針 1 跟指針 2 都從 0 出發：

左圖: 交換後，point 1 會右走一格，point 2 會持續往右走，直到遇到下一個非 0 數字（如右圖）

透過上面這些圖片的演示，可以清楚地看到兩個指標是同方向前進的（都是往右走），只是移動的條件不太一樣。（這裡圖片還是畫得不夠細，建議大家自己逐步畫一次看看。）

同向指針又被稱為 Sliding Window，上面的圖片中也把這題的 window給標示出來了，可以觀察到 point 1 跟 point 2 之間都會是 0。如果不是的話，也就是 point 2 移動到非 0 時，就會進行交換，交換後的 point 1 也會往右走一格，這個維持 window 的過程，用圖示來看，有點像是這個 window 往右滑動了 (slide)，且 window 也可能會變得愈來愈大。

程式碼給大家參考一下：

var moveZeroes = function(nums) {
    const len = nums.length;
    // lastZeroAt 就是上圖中的 point 1
    let lastZeroAt = 0;
    // current 就是上圖中的 point 2
    for(let current = 0; current < len; current++) {
        if(nums[current] !==0 ) {
            [nums[lastZeroAt], nums[current]] = [nums[current], nums[lastZeroAt]];
            lastZeroAt++;
        }
    }
};

這題分析起來就是:

指針移動的「方向」：兩個指針都是往右。
指針移動的「條件」：指針 1 停在最靠近開頭的 0 的位置，每次交換後，就會變成非 0 了，所以要右移動一格。指針 2 一直往右走，但每次走到非 0 數字，就要跟指針 1 交換 → 這裡也可以注意到，還有一個「何時要交換」的判斷 → 維持我們的 window
「停止移動」的條件：當 point 2 已經走完整個陣列，表示整個陣列都已經掃描完畢了，就可以結束了。

到這邊，大家應該也可以發現，指針題型非常需要畫圖，至少我個人是這樣，透過 LeetCode 提供的案例，手動畫圖驗證看看自己的想法，不要一開始就先寫扣，圖像化絕對比程式碼更具體跟好理解一些。

類似題型:

快慢指針

快慢指針的兩個指針大多也是同向的，只是指針的走的速率不太一樣。前文描述的同向指針的範例，感覺上也是兩個指針行進的速度不一樣，point 2 會比 point 1 快，那差別在哪裡呢？我個人的認知是同向指針為了維持 window 確實會有兩個指針前進速率不同的情況，但他是有條件的，也就是要維持那個 window 的條件。而快慢指針則是打從一開始，我們就明定好兩個指針的速率不同，或是其中一個指針慢一點出發。

這邊我們舉三個例子來看看，第一個是 141. Linked List Cycle，這是一題非常非常經典的題目，要求我們要偵測一個 Linked List 是否有「環」（cycle，也就是有一個 node 可以被重複走到），如果有的話，就回傳 true，反之回傳 false。

直接借用 LeetCode 上的圖就是這樣：

這題的做法就是給兩個指標：

slow: 從頭出發，每次只走一格 → 慢指標，走得比較慢
fast: 從頭出發，每次走兩格 → 快指標，走的速率較快
在 fast 走到尾端前，如果 fast 跟 slow 能相遇，表示有 cycle 存在

這題其實是可以數學證明的，有興趣的朋友可以參考這篇 How does Floyd’s slow and fast pointers approach work?

這題可以明顯觀察到，打從一開始，我們就抱定主意，要讓 slow 走得比較（一次只走一格），讓 fast 走得比較快（一次走兩格），跟同向指標是不是不太一樣呢？

var hasCycle = function(head) {
    let slow = head, fast = head;
    
    while (fast && fast.next) {
        // slow 一次走一格
        slow = slow.next;
        // fast 一次走兩格
        fast = fast.next.next;
        // 有相遇表示有 cycle
        if (slow === fast) return true;
    }
    // fast 能把 list 走完，且都沒有跟 slow 相遇，沒有 cycle
    return false;
};

指針移動的「方向」：兩個指針都是往右。
指針移動的「條件」：只要兩個指針還沒有相遇，slow 指針就向右走一格，fast 就向右走兩格。
「停止移動」的條件：當快慢指針相遇或是 fast 指針已經走完整個 list。

快慢指標太經典了，讓我們來看看另外一題 876. Middle of the Linked List，這題是要我們從一個單向 linked list 中找到最中間的那個 node，如果 list 長度是偶數，就回傳第二個。

單向的 Linked List 是很難定位的，他只能一直往右走，且只能知道是否還有下一個 node，不會知道下一個 node 之後的情況，也就是不會知道整條 list 有多長。

反過來想一下，如果這題是陣列，要回傳陣列中間的那個值，你會怎麼做？是不是就是把陣列長度找出來、除以 2，頂多判斷一下奇偶數而已，然後就可以直接回傳該位置的值了。例如:

const len = ary.length;
const middle = Math.floor(len/2);
return ary[middle];
// return ary[Math.floor(ary.length/2)];

那 Linked List 呢？一來你無法知道長度，二來無法靠「index」直接定位，真的要做，只能掃描兩次：

var middleNode = function(head) {
    // 第一次找出長度
    let len = 0, cur = head;
    while(cur != null) {
        len++;
        cur = cur.next;
    }
    // 第二次走到定位
    let middle = Math.floor(len/2);
    cur = head;
    while(middle > 0) {
        middle--;
        cur = cur.next;
    }
    return cur;
};

現在讓我們來試試看快慢指標：一樣 slow 指標一次走一格，fast 指標一次走兩格，如此一來，當 fast 指標走到結束時，slow 就會剛好走到一半，是不是很酷！

var middleNode = function(head) {
    let slow = head;
    let fast = head;
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

另外一種題型則是快慢指針的速率其實一樣，但慢指針慢一點出發，例如 19. Remove Nth Node From End of List，這題是給我們一個單向的 Linked List，再給我們一個數字 n，要我們回傳一個「移除掉從尾端數來第 n 個 node 的 Linked List」。

由上一題我們已經知道，對 Linked List 來說是很難定位的，從前面數就已經不直覺了，這題竟然還要從尾端數 n 個回來？

這時候我們就可以設計兩個指標，第一個 fast 就是一直往右走，當 fast 走了 n 步後，slow 再開始走，當 fast 走到結尾時，slow 就會停在倒數第 n 個 node。為什麼這樣可以找到倒數第 n 個 node 呢？因為當 fast 走了 n 步後，slow 再開始走，表示當 fast 走完、停下來時，slow 會比 fast 少走 n 步，那不就是倒數第 n 個 node 嗎？

比較一下下列兩張圖，應該就可以很清楚地知道了（所以畫圖真的超重要 der~）

是不是很酷！！！

類似的題型:

在各種解題技巧與演算法中，推薦演練雙指針技巧是因為：

雙指針算是不難懂的一種技巧，記得務必搭配畫圖，我個人是覺得雙指針題目會了就會了，不像 Dynamic Programming 或是一些較難的 graph 的演算法題，就算我寫過了，還是很快就忘記了 😅 （可能也表示我並不是真的學會？），或是複雜到其實要在短短的面試時間內解完不太可能…（我是以我的個人解題能力來說，相信有很多大大們可以。）
解題範圍廣，陣列、Linked List 與字串都有可能用上。
在時間與空間複雜度上都能有顯著優化效果的一種技巧，在時間上，往往只需要掃描過一次，空間上，大多是在原陣列上移動，不需要花費太多額外的空間。

之前在 Threads 上有分享過推薦的解題練功過程（連結），無論如何，對陣列、Linked List、String 的操作是基本功，務必要先練好，再練這幾個基本功時，也可以搭配雙指針的題目做進階一點點的練習，會變得必較有趣一些。