雙指標 (Two Pointers)#

很多看似要兩層巢狀迴圈的問題——「找一對和為 target 的數」「判斷回文」「原地去重」——其實只要在資料上佈下兩個指標，協調它們的移動方向與速度，就能一次掃描解決。雙指標（Two Pointers）是所有「指標型技巧」的母章，後面的滑動視窗、快慢指標都是它的特例。

核心思想#

暴力解之所以是 O(n²)，是因為對每個元素都重新掃一遍其餘元素——這正是演算法思維總綱裡說的「無用功」。雙指標的本質，是讓兩個指標各自單調移動、總共只走 O(n) 步，就覆蓋掉原本要 n² 次的配對嘗試。

關鍵在於：每移動一個指標，我們都能確定性地排除掉一整批不可能的答案，而不必逐一驗證。能不能排除一整批，取決於資料是否具備某種「方向性」。

雙指標不是「隨便放兩個 index 同時跑」。它能成立的前提，是移動某個指標會讓某個量單調變化（變大或變小）。沒有這個單調性，兩個指標就退化成普通的雙重迴圈，省不了任何時間。

什麼時候用：三個觸發訊號#

拿到題目時，看到下面這幾個特徵，就可以往雙指標想：

訊號說明為什麼適合
輸入有可預測的動態最典型是「已排序陣列」右移指標必使值變大，可據此單向排除
要找一對／一組值pair sum、回文、容器、三數之和兩個指標天然對應「兩個位置」
線性結構陣列、鏈結串列指標可以沿著線性順序穩定推進

三個訊號裡，「已排序」是最強的觸發器。一旦題目給的是有序陣列、又要找滿足某關係的「一對值」，幾乎可以反射性地嘗試向內收斂雙指標。若題目沒排序但允許排序，先排序再上雙指標往往就對了（代價只是 O(n log n)）。

三種走法#

雙指標依「兩個指標的起點與移動方式」分成三類。

向內收斂（inward）#

兩指標一個在頭（left = 0）、一個在尾（right = n - 1），向中間夾擊，依比較結果決定收哪一側，直到相遇。這是處理「已排序陣列找一對值」的標準形態。

var left = 0
var right = n - 1
while (left < right) {
    // 根據 a[left] 與 a[right] 的關係決定移動哪一側
    if (condition) {
        left++
    } else {
        right--
    }
}

代表題：回文判定、兩數之和（已排序） ↗、盛最多水的容器 ↗。

以**兩數之和（已排序）**為例——為什麼收斂是對的？

fun twoSum(a: IntArray, target: Int): IntArray {
    var left = 0
    var right = a.size - 1
    while (left < right) {
        val s = a[left] + a[right]
        when {
            s == target -> return intArrayOf(left, right)
            s < target  -> left++    // 和太小，只能讓左指標右移變大
            else        -> right--   // 和太大，只能讓右指標左移變小
        }
    }
    return intArrayOf(-1, -1)
}

為什麼 sum < target 時移右指標就是錯的？因為陣列已排序，右移右指標只會讓和更小、更遠離 target。也就是說，當前 right 配上任何比 left 更左的元素都不可能達標——一次移動，排除掉一整列組合。這正是 O(n) 的來源。

同向雙速（讀寫指標）#

兩指標同從左端出發、同向前進，但角色不同：slow 當寫指標，標記「下一個合格元素該放的位置」；fast 當讀指標，掃過每一個元素。常用於原地（in-place）改寫陣列。

var slow = 0
for (fast in 0 until n) {
    if (isKeep(a[fast])) {   // 該保留的元素
        a[slow] = a[fast]
        slow++
    }
}
// slow 即為新陣列長度

代表題：原地移除元素 ↗、移零 ↗、有序陣列去重。

讀寫指標的精髓是「讀和寫解耦」：fast 一路向前讀、絕不回頭；slow 只在遇到要保留的值時才前進並覆寫。兩者都單調右移，所以是 O(n)、且額外空間 O(1)。

分階段（staged）#

兩個指標不同時啟動：第一指標先掃描、定位到某個符合條件的位置，第二指標再從該處延伸處理。它常是前兩種的組合——例如三數之和，就是「先固定一個指標，再對剩餘區間做向內收斂」。

範例：三數之和（3Sum ↗）#

找出所有和為 0 的不重複三元組。思路是降維：外層固定一個數 a[i]，問題就化簡成「在 i 右側的已排序區間裡，找兩數之和為 -a[i]」——正是向內收斂雙指標。

fun threeSum(nums: IntArray): List<List<Int>> {
    nums.sort()                                 // 先排序，才能用向內收斂
    val res = mutableListOf<List<Int>>()
    val n = nums.size
    for (i in 0 until n - 2) {
        if (i > 0 && nums[i] == nums[i - 1]) continue   // 跳過重複的固定值
        if (nums[i] > 0) break                  // 最小值已 > 0，後面不可能湊出 0
        var left = i + 1
        var right = n - 1
        val target = -nums[i]
        while (left < right) {
            val s = nums[left] + nums[right]
            when {
                s == target -> {
                    res.add(listOf(nums[i], nums[left], nums[right]))
                    // 跳過相鄰重複值，避免產生重複三元組
                    while (left < right && nums[left] == nums[left + 1]) left++
                    while (left < right && nums[right] == nums[right - 1]) right--
                    left++
                    right--
                }
                s < target  -> left++
                else        -> right--
            }
        }
    }
    return res
}

去重的關鍵在三個 continue／while 跳過：外層跳過重複的固定值，內層在命中後跳過相鄰相同的 left 與 right。因為陣列已排序，「相同的值一定相鄰」，所以只要比對隔壁元素就能去重，不需額外的 HashSet。總複雜度 O(n²)——外層 O(n)，內層雙指標 O(n)。

為什麼能省下一層迴圈？

樸素的三重迴圈是 O(n³)。固定 a[i] 後，內層的「兩數之和」若用 HashSet 是 O(n)、但要額外空間且難去重；改用向內收斂雙指標，同樣 O(n) 卻是 O(1) 空間、又能借「值相鄰」天然去重。所以排序的 O(n log n) 投資，換來內層從 O(n²) 降到 O(n)，非常划算。

快慢指標（Fast & Slow Pointers）#

快慢指標是雙指標的重要特例：兩個指標同向、但速度不同（慢指標每輪走 1 步，快指標走 2 步）。它解決的是另一類問題——無法用索引隨機存取的結構（如鏈結串列），或「下一個狀態可以由當前狀態算出」的隱式序列。

為什麼能判圈（Floyd 判圈）#

在鏈結串列裡，沒有環時快指標會先抵達 null 而結束；一旦存在環，兩個指標終究都會進到環內。進環之後，把它想成在跑道上追逐：

  • 快指標每輪比慢指標多走 1 步，所以兩者的距離每輪縮短 1；
  • 距離是有限的整數、又每輪 -1，必定歸零——也就是兩指標必定相遇。

用「相遇（==）」而不是「超越（>）」當偵測條件，是因為兩指標移動是離散的跳格。快指標不會「跨過」慢指標而不踩到它——因為距離一次只縮 1，必然會精準落在同一節點。若用「超越」判斷反而可能漏抓。

模板#

var slow = head
var fast = head
while (fast != null && fast.next != null) {   // 同時檢查 fast 與 fast.next，防 null
    slow = slow?.next
    fast = fast.next?.next
    if (slow === fast) {
        // 偵測到環
        ...
    }
}

迴圈條件務必同時檢查 fast != null && fast.next != null。因為快指標一次跳兩格，少檢查任何一個都可能對 null 解參考而拋 NullPointerException。順序也不能反——要先確認 fast 非 null 才能讀 fast.next。

這個模板稍作變化就能解三類問題：

目標做法
偵測是否有環快慢相遇即有環；快指標先到 null 即無環
找中點快指標到底時，慢指標恰在中點
找環的起點相遇後，另起一指標從 head 出發，與慢指標同速前進，再次相遇處即環起點
找中點與找環起點的原理

找中點：快指標走的步數是慢指標的兩倍，所以快指標走完整條（2k 步）時，慢指標恰好走到一半（k 步）——這正是中點。對奇偶長度，依迴圈條件寫法會落在中間或偏右中點。

找環起點：設頭到環起點距離 a，環起點到相遇點距離 b，環長 L。相遇時慢走了 a+b、快走了 a+b+nL，又快是慢的兩倍，可推出 a = nL - b。意思是：從 head 走 a 步、和從相遇點走 a 步，會在環起點會合。所以相遇後讓一個新指標從 head 同速出發，再次相遇即環起點。

範例：快樂數（Happy Number ↗）#

「快樂數」的定義：反覆把一個數各位數字平方和取代自身，若最終會變成 1 就是快樂數，否則會陷入循環。

關鍵洞察：把「各位數平方和」當成隱式的 next() 函數，這個過程就是一條隱式鏈結串列——於是「會不會無限循環」就歸約成判圈問題，直接套快慢指標。

fun isHappy(n: Int): Boolean {
    var slow = n
    var fast = nextState(n)
    while (fast != 1 && slow != fast) {
        slow = nextState(slow)              // 慢走一步
        fast = nextState(nextState(fast))   // 快走兩步
    }
    return fast == 1                        // 到 1 是快樂數；否則快慢相遇，陷入環
}

private fun nextState(x: Int): Int {        // 隱式的「下一個狀態」
    var n = x
    var total = 0
    while (n > 0) {
        val d = n % 10
        total += d * d
        n /= 10                             // Int 整數除法，等同 Python 的 //
    }
    return total
}

這題用 HashSet 記錄看過的數也能做（出現重複即有環），但要 O(n) 額外空間。快慢指標把空間降到 O(1)——這正是 Floyd 判圈相對於「記錄已訪問」的核心優勢：不需要記住走過哪些狀態，只靠相對速度就能偵測環。

小結#

走法指標配置移動規則適用場景
向內收斂一頭一尾，向中間夾依比較收某一側已排序陣列找一對值、回文、盛水容器
同向雙速（讀寫）同從左出發slow 寫、fast 讀原地移除／移零／去重，O(1) 空間
分階段先定位再延伸第一指標定位、第二指標處理三數之和等降維問題
快慢指標同向不同速慢 1 步、快 2 步鏈結串列判圈／找中點／找環起點、隱式序列判圈

判斷該用哪一種，回到「資料的方向性」：值有序 ➡️ 向內收斂；要原地改寫 ➡️ 讀寫指標；不能隨機存取或是隱式序列 ➡️ 快慢指標。掌握這條主線，後續的滑動視窗（同向雙指標 + 維護視窗內狀態）就只是它的自然延伸。需要對映射查找而非位置配對時，則改用雜湊；可與二分查找對照——後者是「單一指標 + 折半」的另一種單調性利用。

Backward 堆疊與佇列 滑動視窗 Forward