Was ist die Zwei-Pointer-Technik?

Question

Accepted Answer

Die **Zwei-Pointer**-Technik nutzt zwei Indizes, die sich durch eine Sequenz bewegen, um Probleme in einem einzigen Durchlauf zu lösen — viele O(n²) Brute-Force-Lösungen werden in **O(n)** umgewandelt.

## Die Idee

Halten Sie zwei Zeiger (oft an den Enden, oder einen langsamen und einen schnellen) und bewegen Sie sie basierend auf einer Bedingung, um die Arbeit zu reduzieren, ohne erneut zu scannen.

## Beispiel: Paare addieren sich zu einem Ziel in einem sortierten 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
```

## Komplexität

- **Zeit:** O(n). **Speicher:** O(1).

## Warum es wichtig ist

Zwei Zeiger ist eines der höchstgenutzten Interview-Muster: Es faltet verschachtelte Schleifen in einen sauberen linearen Scan zusammen.

Es lehrt Sie, Struktur (wie Sortiertheit) zu nutzen, anstatt Brute Force zu verwenden.

Die gleiche Idee treibt Fusionierung, Partitionierung und den Fusionsschritt des Merge Sort an.

## Wann man es verwendet / Fallstricke

Grund für **sortierte Arrays**, Palindrom-Überprüfungen, Umkehrung und Entfernen von Duplikaten an Ort und Stelle. Das Array muss oft für die Variante mit konvergierenden Zeigern sortiert sein. Seien Sie vorsichtig mit Zeiergrenzen und Schleifenbedingung (`lo < hi`).