Co je technika dvou ukazatelů?

Question

Accepted Answer

Technika **dvou ukazatelů** používá dva indexy, které se pohybují posloupností k řešení problémů v jednom průchodu — přeměňuje mnoho řešení O(n²) hrubou silou na **O(n)**.

## Myšlenka

Udržujte dva ukazatele (často na koncích, nebo jeden pomalý a jeden rychlý) a pohybujte je na základě podmínky, zmenšujte práci bez opětovného prohledávání.

## Příklad: párování sčítající se na cíl v seřazeném poli

```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
```

## Složitost

- **Čas:** O(n). **Prostor:** O(1).

## Kdy používat / úskalí

Skvělá pro **seřazená pole**, kontroly palindromu, obrácení a odebírání duplikátů na místě. Pole musí být často seřazeno pro variantu konvergujících ukazatelů. Buďte opatrní s hranicemi ukazatelů a podmínkou smyčky (`lo < hi`).

## Proč na tom záleží

Dva ukazatele jsou jedním z nejvyššího páky vzorů pohovorů: zahrnují vnořené smyčky do čistého lineárního skenování.

Učí vás využívat strukturu (např. řazenost) místo hrubé síly.

Tutéž myšlenku využívá slučování, dělení a krok slučování třídění slučováním.