前言

在演算法題目中，Two Pointers（雙指針）是僅次於 Binary Search 的高頻技巧之一。它的核心是用兩個索引指針在序列中移動，透過控制移動策略優化搜尋效率。

幾乎所有跟Array、String、Linked List相關的題目，只要能透過「縮小搜尋空間」加速，就可能用到這個技巧。

核心概念

設定兩個指標 left 和 right
根據題目條件控制移動方向與邏輯
透過這種「雙指針協同移動」，將時間複雜度下降一個層級

適用條件：

資料是有序結構或能透過條件維護狀態
問題可透過縮小範圍逼近答案
需要同時追蹤兩個位置進行比較或計算

常見模板

1. 同向雙指針（Same Direction / Sliding Window）

兩個指針都從左往右移動，通常用於處理動態視窗區間。

適用場景：

刪除重複元素
快速定位子陣列
控制滑動視窗大小

範例：移除重複元素

def removeDuplicates(nums):
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

2. 相向雙指針（Opposite Direction）

一個指針從左到右，另一個從右到左，向內收縮

適用場景：

求和問題（Two Sum II, Three Sum）
排序陣列找目標組合

範例：Two Sum II

def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]
        elif s < target:
            left += 1
        else:
            right -= 1
    return []

3. 快慢指針（Fast & Slow Pointers）

一個指針移動速度較快，另一個較慢，常用於鏈結串列問題。

適用場景：

檢測鏈結串列是否有環 (Floyd Cycle Detection Algorithm)
找出鏈結串列的中點
刪除倒數第 n 個節點

範例：Linked List Cycle

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

模板選擇總結總結

模板類型	適用場景	範例題目
同向雙指針	移動或壓縮區間問題，例如去重、滑動視窗	Remove Duplicates, Longest Substring Without Repeating Characters
相向雙指針	排序陣列內的組合問題，例如 Two Sum、Three Sum	Two Sum II, Three Sum
快慢指針	鏈結串列操作，例如找環或中點	Linked List Cycle, Middle of the Linked List