Two Pointer 的產生源自於一個核心問題，如何有效處理陣列或者序列中的配對、區間以及範圍搜尋問題。

最初，我們在遇到需要在陣列中尋找配對或者子陣列的問題時，最直觀的方式便是使用雙重迴圈 (nested loops)。例如，在一個陣列中找到兩個數的和等於目標值：

1
2
3
4
5
6
7
for(int i = 0; i < arr.len(); i++){
    for(int j = i + 1; j < arr.len(); j++){
        for(arr[i] + arr[j] == target){
            return [i, j];
        }
    }
}

但是雙重迴圈的方式，導致的後果就是時間複雜度為 $O(n^2)$

相比於暴力解法的「盲目搜尋」，Two Pointer 提供了一種「有方向性的搜尋」策略。

兩者差異在於，暴力解需要檢查所有可能組合，two pointer 需要根據問題特性，有策略性的縮小搜尋範圍。

Key Point

Two Pointer 的產生基於對特定問題特性的觀察：

  • 有序性：當陣列已經排序時，我們可以利用這個特性
  • 單調性：某些條件具有單調性（例如：左指針右移時，和會增大）
  • 互補性：兩個指針的移動可以互相影響，避免重複計算

Two Pointer 有分為兩種：

  • 快慢指標：兩個指標一起指向頭，一個指標按著既有的陣列走，另一個則按照題目需求來移動，讓指標有快慢之分，他們都會朝向同一個方向前進

  • 左右指標：兩個指標分別指向頭尾，在頭的部分會往尾巴移動，在尾的部分則會往頭移動，兩個指標就會逐漸靠近。