Two Pointers 雙指針 ·

介紹
#

雙指針用兩個 index 一起掃描，每一步根據條件決定移動哪一個，讓原本 O(n^2) 的兩兩比較降到 O(n)。

關鍵是每個指針都只往一個方向走：只要能證明「這個位置之後不會再用到」，就可以放心地移動它。

常見的三種形式：

形式	指針怎麼走	例子
對撞指針	一個從頭、一個從尾，往中間靠	回文、反轉、排序後找 pair
兩個序列各一個	各自在自己的序列上往前	合併、比對、子序列判斷
同向快慢	兩個都從頭開始，速度不同	滑動窗口、去重

滑動窗口另外有一篇；同向快慢這篇只講「寫入指針」（模板五），也就是原地刪除、去重、搬移元素。

模板一：對撞指針
#

left, right = 0, len(s) - 1
while left < right:
    if 符合條件(s[left], s[right]):
        處理()
    left += 1
    right -= 1

檢查回文 / 改成回文（LC 2697）：兩端不同時，改成比較小的那個字元，字典序最小。
反轉，但跳過某些字元（LC 3823）：兩邊各自先跳到要處理的字元，再交換。
兩個字串拼成回文（LC 1616）：外側貪心配對，配不下去時，剩下的中間段必須整段來自同一個字串，而且本身是回文。

Python 的字串不能修改，要交換字元得先 list(s)，最後再 "".join(...)（LC 3794）。

跳過不算的字元再比較（LC 125、917、345）：用 if / elif / else 一次只動一邊，兩邊都停在有效字元上才比較或交換。
刪掉一個字元的回文（LC 680）：第一對不同時只有「刪左」和「刪右」兩種，分別檢查剩下的區間。
貪心移動比較矮的一邊（LC 11）：面積受限於比較矮的那一邊，移動比較高的一邊不可能變大。

延伸：k-sum（LC 15、16、18）
#

排序後固定前面 k - 2 個數，最後兩個用對撞指針，O(n^(k-1))。去重要做在三個地方：

nums.sort()
for i in range(n):
    if i > 0 and nums[i] == nums[i - 1]:
        continue                       # 第一個數去重
    l, r = i + 1, n - 1                # 從 i + 1 開始，不是 0
    while l < r:
        s = nums[i] + nums[l] + nums[r]
        if s < target:
            l += 1
        elif s > target:
            r -= 1
        else:
            res.append([nums[i], nums[l], nums[r]])
            l += 1
            while l < r and nums[l] == nums[l - 1]:
                l += 1                 # 找到之後跳過相同的值
            r -= 1

4Sum 多一層 j，它的去重條件是 j > i + 1；3Sum Closest 不用去重，改成比 abs(s - target)。

模板二：兩個序列各一個指針
#

i = j = 0
while i < len(a) and j < len(b):
    if a[i] == b[j]:
        ...
        i += 1
        j += 1
    elif a[i] < b[j]:
        i += 1
    else:
        j += 1
# 處理剩下的部分

合併兩個有序序列（LC 2570）：跟 merge sort 的 merge 一樣。
找共同元素（LC 2540）：比較小的那邊往前。
子序列判斷（LC 522）：相同時兩邊都前進，不同時只有長字串前進。
連續段比對（LC 809）：兩邊各自數出目前這段相同字元有多長，再比較長度。

主要參數說明：
#

迴圈結束後要確認兩邊都用完了：只檢查其中一邊，另一邊剩下的字元會被忽略（LC 809）。
其中一邊先用完時，不能再讀它：讀之前要先檢查 index（LC 2337 的 Runtime Error）。

模板三：跳過空白，比對棋子的位置
#

L 只能往左、R 只能往右、_ 或 X 是空位（LC 2337、777）：

去掉空位之後，兩個字串的棋子順序必須完全一樣（棋子不能互相跨越）。
每一對對應的棋子：L 在起點的位置必須 >= 終點的位置；R 必須 <=。

i = j = 0
while True:
    while i < n and start[i] == "_":
        i += 1
    while j < n and target[j] == "_":
        j += 1
    if i == n or j == n:
        return i == n and j == n
    if start[i] != target[j]:
        return False
    if start[i] == "L" and i < j or start[i] == "R" and i > j:
        return False
    i += 1
    j += 1

只比較字元的數量（Counter）不夠：順序和移動方向都要檢查（LC 777 的第一次 WA）。

模板四：排序後數 pair
#

陣列排序後，固定一端，另一端用指針或 bisect 找出符合條件的範圍：

nums.sort()
left, right = 0, len(nums) - 1
while left < right:
    if nums[left] + nums[right] > target:
        right -= 1                    # 太大，只能縮小最大的那個
    else:
        count += right - left         # left 跟 (left, right] 都可以配
        left += 1

這是 Two Sum 的排序版本，也是很多「數有幾對 pair」題目的骨架。

模板五：寫入指針（原地覆寫）
#

k 指向「下一個要寫入的位置」，i 掃過整個陣列。nums[:k] 永遠是已經處理好、要保留的元素，因為 k <= i，寫入不會蓋掉還沒讀的值：

k = 0
for x in nums:
    if 要保留(x):
        nums[k] = x
        k += 1
return k                               # nums[:k] 是答案

題目	要保留的條件
LC 27 Remove Element	`x != val`
LC 26 Remove Duplicates	`k == 0 or x != nums[k - 1]`
LC 80 最多保留兩個	`k < 2 or x != nums[k - 2]`
LC 283 Move Zeroes	`x != 0`，用交換讓 0 跑到後面
LC 905 Sort Array By Parity	`x` 是偶數，用交換

比較的對象是已經寫入的 nums[k - 1]、nums[k - 2]，不是原本的 nums[i - 1]，後者可能已經被覆寫了（LC 80）。
寫入後會變長的題目（LC 1089 Duplicate Zeros）要從後往前寫，先算出每個元素的最終位置，才不會蓋掉還沒處理的值。
三種值的分類（LC 75 Sort Colors）用三個指針：low 以前是 0、high 以後是 2；跟 high 交換之後 i 不要前進，換過來的值還沒檢查。