👉 Two Pointers

雙指針在有序或對稱結構上往中間或同向移動。

18 題

📖 分類導讀

利用兩個指針在陣列或字串上移動，透過不同起點、方向或速度來高效解決問題。常見模式包括：相向指針（由兩端往中間）、同向指針（快慢指針）。

Notes:

  • 通常需要先排序，或在已排序的資料上操作
  • 相向指針常用於尋找配對，快慢指針常用於偵測環或找中點

三種移動策略

策略指針怎麼動典型用途
相向 (inward)一個從頭、一個從尾，往中間靠已排序陣列找配對（兩數之和）、回文檢查、盛水容器
同向 (unidirectional)兩指針同方向，一個探路、一個記錄寫入位置原地移除/去重、把符合條件的元素往前搬
分階段 (staged)先用一個指針定錨，再從它出發移動另一個三數之和（固定一個再雙指針）、區段切分

之所以能把 O(n^2) 的巢狀枚舉降到 O(n)，是因為輸入具有「可預測的動態」——已排序的單調性、回文的對稱性，讓我們每一步都能確定該移動哪一根指針，而不必回頭重掃。

TIP

訊號詞：「已排序」「找一對 / 三個和為某值」「回文」「原地 (in-place)」「不用額外空間」。看到這些就先想雙指針。

原地反轉技巧

陣列旋轉、反轉子段常用「三次反轉法」：要把 ab 變成 ba，等同 (a^R b^R)^R（各自反轉再整體反轉），全程 O(1) 額外空間。

fun reverse(nums: IntArray, from: Int, to: Int) {
    var l = from
    var r = to
    while (l < r) {
        val t = nums[l]; nums[l] = nums[r]; nums[r] = t
        l++; r--
    }
}

// 將陣列向左旋轉 k 步：reverse 前 k 段、reverse 後段、再整體 reverse
fun rotateLeft(nums: IntArray, k: Int) {
    val n = nums.size
    val s = k % n
    reverse(nums, 0, s - 1)
    reverse(nums, s, n - 1)
    reverse(nums, 0, n - 1)
}

本章深入

跨倉庫導讀

#11Container With Most WaterMedium★★★★★⏱ O(n)#153SumMedium★★★★★⏱ O(n^2)#184SumMedium★★★★★⏱ O(n³)#26Remove Duplicates From Sorted ArrayEasy★★★★★⏱ O(n)#42Trapping Rain WaterHard★★★★★⏱ O(n)#80Remove Duplicates From Sorted Array IIMedium★★★★★⏱ O(n)#88Merge Sorted ArrayEasy★★★★★⏱ O(m + n)#125Valid PalindromeEasy★★★★★⏱ O(n)#167Two Sum II - Input Array Is SortedMedium★★★★★⏱ O(n)#189Rotate ArrayMedium★★★★★⏱ O(n)#283Move ZeroesEasy★★★★★⏱ O(n)#344Reverse StringEasy★★★★★⏱ O(n)#680Valid Palindrome IIEasy★★★★★⏱ O(n)#881Boats to Save PeopleMedium★★★★★⏱ O(n log n)#1498Number of Subsequences That Satisfy The Given Sum ConditionMedium★★★★★⏱ O(n log n)#1768Merge Strings AlternatelyEasy★★★★★⏱ O(n + m)#1968Array With Elements Not Equal to Average of NeighborsMedium★★★★★⏱ O(n log n)#1984Minimum Difference Between Highest And Lowest of K ScoresEasy★★★★★⏱ O(n log n)