Vad är två-pekartekniken?

Question

Accepted Answer

Tekniken med **två pekare** använder två index som rör sig genom en sekvens för att lösa problem i ett enda pass — och förvandlar många O(n²) brute-force-lösningar till **O(n)**.

## Idén

Håll två pekare (ofta i ändarna, eller en långsam och en snabb) och flytta dem baserat på ett villkor, vilket minskar arbetet utan att skanna om.

## Exempel: hitta ett par som summerar till ett målvärde i en sorterad 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
```

## Komplexitet

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

## När du ska använda / fallgropar

Utmärkt för **sorterade arrays**, palindromkontroller, omkastning och borttagning av dubbletter på plats. Arrays måste ofta vara sorterad för varianten med konvergerande pekare. Var försiktig med pekarens gränser och loopvillkoret (`lo < hi`).

## Varför det är viktigt

Två pekare är ett av de mest kraftfulla intervjumönstren: det kollapsar kapslade loopar till en ren linjär genomsökning.

Det lär dig att utnyttja struktur (som sorterad ordning) istället för brute force.

Samma idé driver ihop sammanslagning, partitionering och sammanslagningssteget i merge sort.