Czym jest technika dwóch wskaźników?

Question

Accepted Answer

Technika **dwóch wskaźników** wykorzystuje dwa indeksy poruszające się przez sekwencję, aby rozwiązać problemy w jednym przejściu — zamieniając wiele rozwiązań O(n²) na siłę w **O(n)**.

## Pomysł

Zachowaj dwa wskaźniki (często na końcach, lub jeden wolny i jeden szybki) i poruszaj nimi na podstawie warunku, zmniejszając pracę bez ponownego skanowania.

## Przykład: pary sumujące się do celu w posortowanej tablicy

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

## Złożoność

- **Czas:** O(n). **Przestrzeń:** O(1).

## Kiedy używać / pułapki

Świetnie dla **posortowanych tablic**, kontroli palindromu, odwracania i usuwania duplikatów w miejscu. Tablica musi być często posortowana dla wariantu zbiegających się wskaźników. Uważaj na granice wskaźników i warunki pętli (`lo < hi`).

## Dlaczego to ważne

Dwaj wskaźniki to jeden z najbardziej pożytecznych wzorców rozmowy kwalifikacyjnej: zwija zagnieżdżone pętle w czyste skanowanie liniowe.

Uczy cię wykorzystywać strukturę (jak posortowanie) zamiast siły.

Ta sama idea napędza scalanie, partycjonowanie i krok scalania sortowania przez scalanie.