Ce este tehnica doi pointeri?

Question

Accepted Answer

Tehnica **doi pointeri** folosește doi indici care se mișcă printr-o secvență pentru a rezolva probleme într-o singură trecere — transformând multe soluții O(n²) de forță brută în **O(n)**.

## Ideea

Pastrați doi pointeri (adesea la capete, sau uno lent și unu rapid) și mutați-i pe baza unei condiții, restrângând munca fără rescannare.

## Exemplu: perechi care se sumează la o țintă într-un tablou sortat

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

## Complexitate

- **Timp:** O(n). **Spațiu:** O(1).

## Când se folosește / capcane

Excelent pentru **tablouri sortate**, verificări de palindroame, inversare și eliminarea duplicatelor în loc. Tabloul trebuie adesea sortat pentru varianta pointeri convergenți. Fiți atenți la limitele pointerului și la condiția buclei (`lo < hi`).

## De ce este important

Doi pointeri este unul din cele mai avantajoase modele de interviu: preschimbă buclele imbricate într-o scanare liniară curată.

Vă învață să exploatați structura (cum ar fi sortarea) în loc de forță brută.

Aceași idee alimentează fuzionarea, partiționarea și pasul de fuzionare al sortării fuzionării.