Overview
Zwei Zeiger konvergieren von außen nach innen (oder einer läuft schneller) um Paare oder Teilmengen in O(n) zu finden.
Analogy
Zwei Personen laufen von beiden Enden einer Brücke aufeinander zu – sparen die Hälfte des Weges.
Step-by-step
- Für gegenläufige Zeiger: Array sortieren, l=0, r=len-1.
- Prüfe Bedingung (z.B. Summe), bewege l++ wenn zu klein, r-- wenn zu groß.
- Stoppe wenn l>=r.
Visual
[-2,1,3,5] target=4: l=-2,r=5→sum=3<4→l++; l=1,r=5→sum=6>4→r--; l=1,r=3→sum=4→gefunden
Common mistakes
- Zwei-Zeiger-Technik ohne vorheriges Sortieren kann falsche Ergebnisse liefern.
- Fast/Slow Zeiger für Zykelerkennung: beide starten an head, nicht an verschiedenen Stellen.
Practice questions
- 2Sum mit sortiertem Array lösen.
- Zykus in verlinkter Liste mit Floyd's Algorithmus erkennen.
Time
O(n log n) inkl. Sortierung, O(n) Zwei-Zeiger-Phase