[algorithms] Two Pointers 雙指標

視覺化概覽

flowchart TD
    A["已排序陣列\nleft=0, right=n-1"] --> B["計算 sum =\narr[left] + arr[right]"]
    B --> C{"sum == target？"}
    C -->|"是 ✓"| D["找到答案！"]
    C -->|"否"| E{"sum < target？"}
    E -->|"是：需要更大的值"| F["left →\nleft++"]
    E -->|"否：需要更小的值"| G["← right\nright--"]
    F --> H{"left < right？"}
    G --> H
    H -->|"是"| B
    H -->|"否"| I["無解"]

    style F fill:#2196F3,color:#fff
    style G fill:#2196F3,color:#fff

什麼是雙指標？

用兩個指標遍歷，減少巢狀迴圈。

暴力 O(n²) → 雙指標 O(n)

三種類型

1. 對撞指標

從兩端向中間靠攏：

[2, 7, 11, 15]  target=9
 ↑          ↑
left       right

2 + 15 = 17 > 9 → right--
2 + 11 = 13 > 9 → right--
2 + 7 = 9 ✓

while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) return result;
    if (sum < target) left++;
    else right--;
}

2. 快慢指標

同向不同速：

移除值為 3：
[3, 2, 2, 3]
 ↑
slow, fast

[2, 2, 2, 3]  fast 找到非 3，放到 slow 位置
    ↑  ↑
 slow fast

int slow = 0;
for (int fast = 0; fast < n; fast++) {
    if (nums[fast] != val) {
        nums[slow++] = nums[fast];
    }
}

3. 滑動視窗

維護動態區間（另有專題）

對撞指標應用

兩數之和（已排序）

int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return new int[]{left, right};
        if (sum < target) left++;
        else right--;
    }
    return null;
}

三數之和

固定一個數，剩下兩個用雙指標：

for (int i = 0; i < n - 2; i++) {
    // 跳過重複
    if (i > 0 && nums[i] == nums[i-1]) continue;
 
    int left = i + 1, right = n - 1;
    while (left < right) {
        // 雙指標找 -nums[i]
    }
}

盛水容器

|       |       |
|   |   |   |   |
|   |   |   |   |   |
面積 = min(高度) × 寬度

策略：移動較矮的指標

回文判斷

while (left < right) {
    if (s.charAt(left) != s.charAt(right)) return false;
    left++;
    right--;
}

快慢指標應用

移除元素

int slow = 0;
for (int fast = 0; fast < n; fast++) {
    if (nums[fast] != val) {
        nums[slow++] = nums[fast];
    }
}
return slow;

移除重複

int slow = 1;
for (int fast = 1; fast < n; fast++) {
    if (nums[fast] != nums[fast-1]) {
        nums[slow++] = nums[fast];
    }
}

移動零

int slow = 0;
for (int fast = 0; fast < n; fast++) {
    if (nums[fast] != 0) {
        swap(nums, slow++, fast);
    }
}

鏈表快慢指標

檢測環

ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true;  // 有環
}
return false;

找環入口

相遇後，從頭和相遇點同時走，再次相遇就是入口

找中點

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
return slow;  // 中點

找倒數第 k 個

// fast 先走 k 步
for (int i = 0; i < k; i++) fast = fast.next;
 
// 同時走到底
while (fast != null) {
    slow = slow.next;
    fast = fast.next;
}
return slow;

時間複雜度

問題	暴力	雙指標
兩數之和	O(n²)	O(n)
三數之和	O(n³)	O(n²)
移除元素	O(n)	O(n)
環檢測	O(n) 空間	O(1) 空間

經典題目

1. 兩數之和 II - LeetCode 167
2. 三數之和 - LeetCode 15
3. 盛水容器 - LeetCode 11
4. 移除元素 - LeetCode 27
5. 移動零 - LeetCode 283
6. 環形鏈表 - LeetCode 141
7. 環形鏈表 II - LeetCode 142
8. 鏈表中點 - LeetCode 876

相關檔案

• Java 實作：TwoPointers.java