Hva er two-pointer-teknikken?

Question

Accepted Answer

**Two-pointer**-teknikken bruker to indekser som beveger seg gjennom en sekvens for å løse problemer i en enkelt gjennomgang — mange O(n²) brute-force-løsninger blir til **O(n)**.

## Ideen

Behold to pekere (ofte i endene, eller en sakte og en rask) og flytt dem basert på en betingelse, og krympe arbeidet uten å skanne på nytt.

## Eksempel: tallpar som summerer til et mål i en sortert array

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

## Kompleksitet

- **Tid:** O(n). **Plass:** O(1).

## Når det skal brukes / fallgruver

Flott for **sorterte arrays**, palindromkontroller, reversering og fjerning av duplikater på stedet. Arrayen må ofte sorteres for den konvergerende pekervarianten. Vær forsiktig med pekeravgrensninger og løkkebetingelsen (`lo < hi`).

## Hvorfor det er viktig

Two-pointer er et av de høyest-gjennomslag interviewmønstrene: det kollapser nestet løkker til en ren lineær skanning.

Det lærer deg å utnytte struktur (som sorterthet) i stedet for brute force.

Den samme ideen driver sammenslåing, partisjonering og sammenslåingstrinn i merge sort.