Zwei-Zeiger-Technik und Gleitendes Fenster

Kurz: Zwei-Zeiger-Technik und gleitendes Fenster sind Muster, mit denen sich viele Aufgaben auf Listen in einem Durchlauf (O(n)) statt mit verschachtelten Schleifen (O(n²)) lösen lassen.

Genauer: Bei zwei Zeigern laufen zwei Indizes durch die Liste, etwa von beiden Enden aufeinander zu. Beim gleitenden Fenster wächst und schrumpft ein Bereich über die Liste, und man verwaltet die Summe oder Zählung im Fenster.

Im Detail

• Beispiel zwei Zeiger: In einer sortierten Liste zwei Zahlen finden, die eine Summe ergeben: links und rechts beginnen, bei zu großer Summe rechts verkleinern, bei zu kleiner links vergrößern.
• Beispiel Fenster: Längster Teilstring ohne Wiederholung: Fenster erweitern, bei Wiederholung von links verkürzen.
• Palindrom prüfen: Zeiger an beiden Enden, nach innen laufen.
• Voraussetzung: Oft sortierte Daten oder Aufgaben mit zusammenhängenden Abschnitten.
• Laufzeit: Jeder Zeiger geht höchstens einmal durch die Liste: O(n).

Siehe auch: Big-O-Notation, Arrays