Two Pointers 模板

──────────────────────────────────────────────────────────────────────

雙指針有三種完全不同的用法，先認出是哪一種，code 就寫得出來。

對撞指針：一頭一尾往中間走

前提是陣列有序（或問題本身對稱，如回文）。每一步都靠比較決定移動哪一邊 — 這一步就是把 $O(n^2)$ 降到 $O(n)$ 的地方。

left, right = 0, len(nums) - 1
while left < right:
    total = nums[left] + nums[right]
    if total == target:
        return [left, right]
    elif total < target:
        left += 1                # 需要更大 → 左邊往右
    else:
        right -= 1               # 需要更小 → 右邊往左

例題：167. Two Sum II、125. Valid Palindrome、11. Container With Most Water、42. Trapping Rain Water

3 Sum：固定一個數，剩下的用對撞

排序後固定第一個數，對剩下的區間跑對撞指針，注意跳過重複：

nums.sort()
for i in range(len(nums) - 2):
    if i > 0 and nums[i] == nums[i - 1]:
        continue                 # 跳過重複的第一個數
    left, right = i + 1, len(nums) - 1
    while left < right:
        ...
        # 找到答案後，兩邊都要跳過重複
        while left < right and nums[left] == nums[left + 1]:
            left += 1

例題：15. 3 Sum

快慢指針：同向，但速度不同

一個負責「看」，一個負責「寫」。原地移除/去重時，慢指針就是下一個該寫入的位置：

slow = 0
for fast in range(len(nums)):
    if nums[fast] != val:        # fast 看到要保留的元素
        nums[slow] = nums[fast]  # slow 負責寫
        slow += 1
return slow                      # 新長度

例題：26. Remove Duplicates from Sorted Array、283. Move Zeroes

在 Linked List 上，快慢指針改成「一次走一步 / 一次走兩步」，用來找中點和判環 — 見 Linked List 模板。

分區指針：三路劃分

要把陣列分成三段（小於 / 等於 / 大於）時，用三個指針一次掃完：

low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
    if nums[mid] < pivot:
        nums[low], nums[mid] = nums[mid], nums[low]
        low += 1; mid += 1
    elif nums[mid] > pivot:
        nums[mid], nums[high] = nums[high], nums[mid]
        high -= 1            # 換過來的還沒看過，mid 不動
    else:
        mid += 1

high 那條分支 mid 不能加 — 這是最容易寫錯的一行。

例題：75. Sort Colors

面試時的講法

先問「陣列有沒有排序」。有序 → 對撞指針；要原地改陣列 → 快慢指針；要分類 → 分區指針。如果無序而且必須排序才能做，記得把排序的 $O(n\log n)$ 算進總複雜度，並跟面試官確認可不可以改動輸入。

其他例題：680. Valid Palindrome II、88. Merge Sorted Array

更多題目 → #Two Pointers