Što je teknika dva pokazivača?

Question

Accepted Answer

Teknika **dva pokazivača** koristi dva indeksa koji se kreću kroz niz za rješavanje problema u jednom prolazu — pretvarajući mnoga O(n²) rješenja s brute-force pristupom u **O(n)**.

## Ideja

Zadržite dva pokazivača (često na krajevima, ili jedan spora i jedan brz) i pomičite ih na temelju uvjeta, smanjujući rad bez ponovnog skeniranja.

## Primjer: pronalaženje para koji se zbrajaju na cilj u sortiranom nizu

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

- **Vrijeme:** O(n). **Prostor:** O(1).

## Kada koristiti / zamke

Odličan za **sortirane nizove**, provjere palindroma, obrtanje i uklanjanje duplikata na mjestu. Niz mora često biti sortiran za varijantu konvergirajućih pokazivača. Pazite na granice pokazivača i uvjet petlje (`lo < hi`).

## Zašto je to važno

Dva pokazivača jedan su od najprinosnijih obrazaca za intervjue: sažima ugniježđene petlje u čist linearni pregled.

Uči vas da iskoristite strukturu (kao što je sortiranost) umjesto grube sile.

Ista ideja omogućava spajanje, particioniranje i korak spajanja u merge sortu.