Hvad er to-pointer-teknikken?

Question

Accepted Answer

**To-pointer**-teknikken bruger to indekser, der bevæger sig gennem en sekvens for at løse problemer i et enkelt pass — og omdanner mange O(n²) brute-force-løsninger til **O(n)**.

## Idéen

Hold to pointere (ofte ved enderne, eller en langsom og en hurtig) og flyt dem baseret på en betingelse, hvilket formindsker arbejdet uden at genoptage.

## Eksempel: parringssum til et mål i et sorteret 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). **Plads:** O(1).

## Hvornår skal du bruge det / faldgruber

Gode til **sorterede arrays**, palindrom-kontroller, reversering og fjernelse af duplikater på plads. Arrayet skal ofte sorteres til varianten med konvergerende pointere. Vær forsigtig med pointer-grænser og sløjfebetingelse (`lo < hi`).

## Hvorfor det betyder noget

To pointere er et af de højest gearede interviewmønstre: det sammenfolder indlejrede sløjfer til en ren lineær scanning.

Det lærer dig at udnytte struktur (såsom sorteringsevne) i stedet for brute force.

De samme ide driver sammenlægning, partitionering og fusionstrinet i fletningssort.