Mi az két-mutató technika?

Question

Accepted Answer

A **két-mutató** technika két indexet használ, amelyek egy sorozaton keresztül mozognak a problémák egyetlen menetben történő megoldásához — számos O(n²) brute-force megoldást **O(n)** megoldássá alakít.

## Az ötlet

Tartson két mutatót (gyakran a végeken, vagy egy lassú és egy gyors), és mozgassa őket egy feltétel alapján, csökkentve a munkát újraszkennelés nélkül.

## Példa: egy párnak a célt összegezni egy rendezett tömbben

```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               # need a bigger sum
        else:
            hi -= 1               # need a smaller sum
    return None

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

## Bonyolultság

- **Idő:** O(n). **Hely:** O(1).

## Mikor kell használni / csapdák

Kiváló **rendezett tömbök**, palindrom-ellenőrzések, fordítás és duplikátumok eltávolítása helyben. A tömb gyakran rendezettnek kell lennie a konvergens-mutató változathoz. Vigyázzon a mutatók határaira és a hurok feltételére (`lo < hi`).

## Miért fontos

A két-mutató az egyik legmagasabb haszonnal járó interjúminta: az egymásba ágyazott hurkokat tiszta lineáris vizsgálatba zsugorítja.

Megtanítja, hogy a szerkezetet (például a rendezettséget) a brute-force helyett kihasználja.

Ugyanez az ötlet működteti az egyesítést, a particionálást és az összevonási sorrend egyesítési lépését.