Kas yra dviejų rodyklių technika?

Question

Accepted Answer

**Dviejų rodyklių** technika naudoja dvi indeksus, kurie juda per seką, norint išspręsti problemas vienu praėjimu — daugelį O(n²) brute-force sprendimų paverčiant **O(n)**.

## Idėja

Palaikykite dvi rodykles (dažnai galuose arba vieną lėtą ir vieną greitą) ir judinkite jas pagal sąlygą, sumažindami darbą be perskenavimo.

## Pavyzdys: poros, kurios suma lygi tikslui, paieška surūšiuotame masyve

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

## Sudėtingumas

- **Laikas:** O(n). **Erdvė:** O(1).

## Kada naudoti / pavojai

Puikiai tinka **surūšiuotiems masyvams**, palindromo patikrai, inversijoms ir pasikartojimų šalinimui vietoje. Masyvas dažnai turi būti surūšiuotas konverguojančios rodyklės variantui. Saugokitės rodyklės ribų ir kilpos sąlygos (`lo < hi`).

## Kodėl tai svarbu

Dviejų rodyklių technika yra vienas iš svarbiausių pokalbio šablonų: ji suploja įdėtus ciklus į švarias tiesinį skenavimą.

Ji jus moko išnaudoti struktūrą (pvz., rūšiavimą) vietoj žiaurios jėgos.

Ta pati idėja varykina sąjungą, skaidymą ir merge sort suliejimo žingsnį.