Two Pointers
雙指標（Two Pointers）是一種用兩個索引（指標）同時在陣列或字串上移動來解題的技巧，通常能把原本需要雙層迴圈的 O(n^2) 暴力解，降到只需要單層迴圈的 O(n)。
白話理解
想像在一本很厚、已經按頁碼排好序的電話簿裡，找兩個加起來等於某個數字的頁碼。與其每一頁都跟其他頁兩兩配對（暴力法），不如一根手指放在最前面、一根手指放在最後面，往中間慢慢逼近，效率會好上非常多。
兩種常見手法
1. 相向雙指標（Opposite Direction）
一個指標從最前面開始，一個指標從最後面開始，往中間逼近，通常用在已排序的陣列上。
- Python
- JavaScript
- Java
def two_sum(numbers, target):
# 前提：numbers 已經是排序好的陣列
left = 0
right = len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left, right] # 找到了
elif total < target:
left += 1 # 總和太小，把左指標往右移，讓數字變大一點
else:
right -= 1 # 總和太大，把右指標往左移，讓數字變小一點
return [-1, -1] # 找不到
function twoSum(numbers, target) {
// 前提：numbers 已經是排序好的陣列
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) {
return [left, right]; // 找到了
} else if (sum < target) {
left++; // 總和太小，把左指標往右移，讓數字變大一點
} else {
right--; // 總和太大，把右指標往左移，讓數字變小一點
}
}
return [-1, -1]; // 找不到
}
class Solution {
public static int[] twoSum(int[] numbers, int target) {
// 前提：numbers 已經是排序好的陣列
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left, right}; // 找到了
} else if (sum < target) {
left++; // 總和太小，把左指標往右移，讓數字變大一點
} else {
right--; // 總和太大，把右指標往左移，讓數字變小一點
}
}
return new int[]{-1, -1}; // 找不到
}
}
逐步拆解：以 numbers = [2, 7, 11, 15]、target = 9 為例
| 輪次 | left | right | numbers[left] + numbers[right] | 判斷 | 動作 |
|---|---|---|---|---|---|
| 1 | 0 (2) | 3 (15) | 2 + 15 = 17 | 17 > 9，太大了 | right-- |
| 2 | 0 (2) | 2 (11) | 2 + 11 = 13 | 13 > 9，太大了 | right-- |
| 3 | 0 (2) | 1 (7) | 2 + 7 = 9 | 剛好等於 target！ | 回傳 [0, 1] |
因為陣列已經排序好，只要總和太大就代表「右邊的數字太大」，往左移一定會變小；反之總和太小就往右移。每一步都朝正確方向逼近，全程只掃過陣列一次。
注意
這個手法的前提是陣列必須已經排序好。如果陣列是亂序的，sum < target 不代表移動 left 一定能讓總和變大（因為右邊可能還有更小的數字），這時候需要先排序，或改用 Hash Table 來解（用空間換時間）。
2. 同向雙指標（Same Direction，又稱 Fast & Slow Pointers）
兩個指標從同一端出發，但移動速度不同，常用在 Linked List 相關問題。
最經典的應用是判斷 Linked List 是否有環，也就是 Floyd's Cycle Detection（又稱龜兔賽跑演算法）：
- Python
- JavaScript
- Java
def has_cycle(head):
slow = head # 龜：一次走一步
fast = head # 兔：一次走兩步
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: # 兩者相遇，代表有環
return True
return False # fast 先走到底（None），代表沒有環
function hasCycle(head) {
let slow = head; // 龜：一次走一步
let fast = head; // 兔：一次走兩步
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true; // 兩者相遇，代表有環
}
return false; // fast 先走到底（null），代表沒有環
}
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
class Solution {
public static boolean hasCycle(ListNode head) {
ListNode slow = head; // 龜：一次走一步
ListNode fast = head; // 兔：一次走兩步
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true; // 兩者相遇，代表有環
}
return false; // fast 先走到底（null），代表沒有環
}
}
白話理解
如果操場跑道是一個圈（有環），跑得快的人（fast）遲早會從後面追上跑得慢的人（slow），兩人一定會在某一點相遇；如果跑道是一直線（沒有環），跑得快的人會先抵達終點，不會有相遇的機會。
除了判斷「有沒有環」，還可以進一步找出「環的起點」，這部分的推導與完整實作寫在 Floyd's Cycle Detection 裡，歡迎前去參考。
複雜度
| 手法 | 時間複雜度 | 空間複雜度 |
|---|---|---|
| 相向雙指標 | O(n) | O(1) |
| 同向雙指標（Fast & Slow） | O(n) | O(1) |
兩者都只需要常數個額外變數（幾個指標），完全不需要像 Hash Table 那樣額外的儲存空間，這也是雙指標技巧最大的優勢。
適用情況
- 已排序陣列中找符合條件的配對：例如兩數之和（Two Sum，排序後版本）、三數之和（3Sum）。
- 判斷迴文（Palindrome）：從頭尾同時往中間檢查字元是否對稱。
- 盛水問題：Leetcode: Container With Most Water，從最外側開始，每次移動較短的那一邊。
- Linked List 相關問題：判斷是否有環、找出環的起點、找出中點（快指標到底時，慢指標剛好在中間）、找出倒數第 k 個節點。
- 原地移除或去除重複元素：例如移除陣列中的特定值、移除已排序陣列中的重複元素，用一個指標記錄「目前處理到哪」、一個指標記錄「下一個有效位置」。
常見誤區
- 在未排序的陣列上直接套用相向雙指標：如前面提醒的，這個手法高度仰賴「已排序」這個前提，用在亂序資料上邏輯會整個失效。
- Fast & Slow Pointers 速度設反：一定是
fast走得比slow快（通常一次 2 步、slow 一次 1 步），如果兩者速度一樣，永遠不會相遇（在有環的情況下也一樣會一直繞圈错过彼此）。 - 忘記檢查邊界：使用 Fast & Slow Pointers 時，如果沒有同時檢查
fast和fast.next是否存在，容易在鏈結串列長度為奇數或偶數時，對null取.next而出錯。 - 搞混「移動哪一個指標」的方向：相向雙指標中，移動的判斷邏輯（該讓
left前進還是right後退）要對應題目的目標，寫之前建議先想清楚「往哪個方向移動，才會讓結果往正確方向逼近」。