Two Pointers雙指標
對撞指標與同向指標。
用在：有序陣列配對、去重、回文判斷
01為什麼需要它
一份依金額排序的交易紀錄，要找兩筆加起來等於某個對帳金額。暴力是每一筆配每一筆，n(n−1)/2 對，O(n²)。
為什麼用它資料有序就有結構可以用：最小加最大太小，表示最小配誰都不夠，直接淘汰；太大就淘汰最大。一左一右往中間夾，每步淘汰一個，最多 n − 1 步就結束。這是有序配對的標準解法。
一個排好序的陣列裡有重複，要把重複去掉，而且不能開新陣列（記憶體受限或介面要求原地）。
為什麼用它一個指標往前讀，一個指標記「寫到哪了」。讀指標永遠不慢於寫指標，所以覆寫不會弄壞還沒讀的資料。這是同向雙指標，O(n) 時間、O(1) 額外空間。
判斷一個字串正著讀反著讀一樣；或把兩份各自有序的清單合成一份有序的。
為什麼用它回文是從兩端往中間比，合併是兩個指標各在一份清單上往前走。它們都是「用兩個位置的關係推進」，不需要巢狀迴圈。
看到這些關鍵字就想到它：已排序、配對、兩端往中間、原地修改、O(n²) 的雙迴圈裡兩個索引有單調關係。
02核心概念
雙指標是一種把兩層迴圈壓成一層的技巧：兩個索引在陣列上移動，但每一步都只往一個方向走，總移動距離加起來不超過 2n，所以是 O(n)。暴力雙迴圈之所以 O(n²)，是因為外層每換一個位置，內層就重新掃一整段；雙指標能省下來，是因為問題有某種單調性讓「回頭」變得沒必要。
對撞指標：一個從最左、一個從最右往中間走。以有序陣列兩數之和為例，a[l] + a[r] 太小時，a[r] 已是剩下最大的，a[l] 無論配剩下的誰都不夠（和已淘汰元素的配對早就排除了），可以安全丟掉；太大時同理丟掉 a[r]。每一步都淘汰一個元素，且淘汰是有證明的，這才是它正確的原因，不是「看起來合理」。前提是資料有序，無序資料要先排序，或改用雜湊表。注意排序會打亂原本的索引，題目要回傳原索引（例如 LeetCode 1）時，要連索引一起排，或直接用雜湊表。
同向指標（快慢指標）：兩個指標都往右，一個讀一個寫，或一個探路一個跟隨。移除重複時，w 是下一個寫入位置，r 往前讀，a[r] 和上一個保留值不同就寫進 a[w]。因為 w ≤ r 恆成立，覆寫的永遠是已經讀過的格子。搬移零、過濾、壓縮字串，都是同一個骨架。
和滑動視窗的關係：滑動視窗就是同向雙指標，兩個指標之間的區間有特別意義（視窗）。和二分搜尋的關係：兩者都靠有序性，二分一次砍一半找一個位置，雙指標一次淘汰一個找一對。三數之和是把一層迴圈固定住，裡面跑對撞指標，O(n²) 取代 O(n³)。
03演算法步驟
- 1對撞指標先問：資料有序嗎？無序而題目允許排序就先排（O(n log n)），不允許就考慮雜湊表。同向指標的搬移零、過濾這類題目不需要有序。
- 2對撞：
l = 0，r = n − 1，while l < r。比較a[l] + a[r]和目標。 - 3太小
l += 1，太大r −= 1，相等就是答案。每步問自己：被淘汰的那個，為什麼配任何人都不行？ - 4同向：
w = 0（或 1），for r in range(n)。a[r]該保留就a[w] = a[r]; w += 1。 - 5結束時對撞指標回傳找到的一對或「沒有」，同向指標回傳
w，a[:w]是結果。
04互動示範
「對撞」模式在有序陣列找兩數之和 25，劃掉的格子是被證明不可能的。「同向」模式原地移除重複，綠色是已寫好的結果、黃色是正在讀的位置，注意 w 永遠不超過 r。
劃掉的格子已被證明不可能是答案的一部分，之後不會再看。
05程式碼
對撞指標的兩數之和、同向指標的移除重複，以及固定一個數再對撞的三數之和。三數之和的去重是最容易寫錯的地方，看清楚兩處跳過重複的位置。
# 對撞指標：有序陣列兩數之和，回傳 0-based 索引
# （LeetCode 167 要的是 1-based，交出去前兩個各加 1）
def two_sum_sorted(nums, target):
l, r = 0, len(nums) - 1
while l < r:
s = nums[l] + nums[r]
if s == target:
return [l, r]
if s < target:
l += 1 # nums[l] 配最大的都不夠，淘汰它
else:
r -= 1 # nums[r] 配最小的都太大，淘汰它
return [-1, -1]
# 同向指標：原地移除有序陣列的重複（LeetCode 26），回傳新長度
# w 是「下一個要寫的位置」，r 負責讀
def remove_duplicates(nums):
if not nums:
return 0
w = 1
for r in range(1, len(nums)):
if nums[r] != nums[w - 1]: # 和上一個保留的不同才是新值
nums[w] = nums[r]
w += 1
return w # nums[:w] 是結果
# 對撞指標的另一個經典：三數之和（LeetCode 15）
# 排序後固定一個數，剩下的用兩數之和夾
def three_sum(nums):
nums.sort()
out = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # 跳過重複的第一個數
l, r = i + 1, len(nums) - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
out.append([nums[i], nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1 # 跳過重複的第二個數
return out
if __name__ == "__main__":
print(two_sum_sorted([2, 3, 5, 8, 11, 14, 17, 21], 25)) # [3, 6]
a = [1, 1, 2, 2, 2, 3, 5, 5, 6, 6]
n = remove_duplicates(a)
print(a[:n]) # [1, 2, 3, 5, 6]
print(three_sum([-1, 0, 1, 2, -1, -4])) # [[-1, -1, 2], [-1, 0, 1]]06練習題
- LeetCode 167Two Sum II - Input Array Is SortedMedium
- LeetCode 26Remove Duplicates from Sorted ArrayEasy
- LeetCode 283Move Zeroes（同向：讀寫指標）Easy
- LeetCode 125Valid PalindromeEasy
- LeetCode 153SumMedium
- LeetCode 11Container With Most Water（淘汰矮的那邊）Medium