Mikä on kaksiosoittimen tekniikka?

Question

Accepted Answer

**Kaksiosoittimen** tekniikka käyttää kahta indeksiä, jotka liikkuvat jonon läpi ongelmien ratkaisemiseksi yhdessä läpäisyssä — muuttaen monet O(n²) väkivaltaiset ratkaisut **O(n)** ratkaisuiksi.

## Ajatus

Pidä kaksi osoitinta (usein päissä, tai yksi hidas ja yksi nopea) ja siirrä niitä ehdon perusteella, pienentäen työtä ilman uudelleenskannaamista.

## Esimerkki: parien summa tavoitteeseen järjestetyissä taulukossa

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

## Monimutkaisuus

- **Aika:** O(n). **Tila:** O(1).

## Milloin käyttää / Sudenkuopat

Loistava **järjestetyille taulukoille**, palindromintarkistuksille, kääntämiselle ja päällekkäisyyksien poistamiselle paikallaan. Taulukko on usein järjestettävä konvergoivien osoittimien varianttia varten. Ole varovainen osoitinrajoilla ja silmukan ehdolla (`lo < hi`).

## Miksi se on tärkeää

Kaksiosoitin on yksi korkeimmasta vipuvaikutuksesta olevista haastattelun malleista: se tiivistää sisäkkäiset silmukat puhtaaksi lineaariseksi skannaukseksi.

Se opettaa sinulle hyödyntämään rakennetta (kuten järjestystä) brute forcen sijaan.

Sama idea ajaa yhdistämistä, osiointia ja yhdistämislajittelun yhdistymisvaiheita.