Kaj je tehnika z dvema kazalcema?

Question

Accepted Answer

Tehnika **dveh kazalcev** uporablja dva indeksa, ki se premikata skozi zaporedje, da reši probleme v enem samem prehodu — kar spremeni številne O(n²) brute-force rešitve v **O(n)**.

## Ideja

Imej dva kazalca (pogosto na koncih ali enega počasnega in enega hitrega) in ju premikaj glede na pogoj, kar zmanjša količino dela brez ponovnega skeniranja.

## Primer: iskanje para, ki se sešteje v ciljno vrednost v sortiranem 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
```

## Časovna in prostorska zahtevnost

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

## Kdaj uporabiti / pasti

Odlično za **sortirane nize**, preverjanje palindroma, obračanje in odstranjevanje dvojnikov na mestu. Niz mora biti pogosto sortiran za varianto s konvergentnimi kazalci. Pozor na meje kazalcev in pogoj zanke (`lo < hi`).

## Zakaj je to važno

Dveh kazalcev je eden izmed najbolj vplivnih vzorcev pri intervjujih: zgrne gnezdene zanke v čist linearni pregled.

Uči te izkoriščati strukturo (kot je sortiranost) namesto brute force pristopa.

Enaka ideja poganja tudi združevanje, particioniranje in korak združevanja merge sorta.