two-pointer technique とは何ですか？

Question

Accepted Answer

**Two-pointer** technique は、sequence 内を動く 2 つの index を使い、多くの O(n²) brute-force solution を **O(n)** に変える pattern です。

## 考え方

2 つの pointer（両端から、または slow/fast）を保ち、condition に応じて動かします。再 scan せずに work を縮めます。

## 例: sorted array で target sum の pair を探す

```python
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)       # found the pair
        elif s < target:
            lo += 1               # より大きい sum が必要
        else:
            hi -= 1               # より小さい sum が必要
    return None

two_sum_sorted([1, 3, 4, 6, 9], 10)   # -> (1, 3) for 4 + 6
```

## Complexity

- **Time:** O(n)。**Space:** O(1)。

## いつ使うか / pitfalls

**sorted arrays**、palindrome check、reversing、in-place duplicate removal に向きます。converging-pointer variant では array が sorted であることが多く必要です。pointer bounds と loop condition（`lo < hi`）に注意します。

## なぜ重要なのか

two pointers は interview で非常に leverage の高い pattern です。nested loops を clean linear scan に collapse します。sortedness のような structure を使う発想を教え、merging、partitioning、merge sort の merge step にもつながります。