Overview
Fenster fester oder variabler Größe, das über ein Array gleitet, um Teilsequenzen in O(n) zu verarbeiten.
Analogy
Durch ein Zugfenster schauen: der Ausblick ändert sich, wenn der Zug fährt – Elemente treten ein und aus.
Step-by-step
- Festes Fenster: initialisiere Summe der ersten k Elemente.
- Gleite: subtract arr[i-k], add arr[i] – O(1) pro Schritt.
- Variables Fenster: expandiere rechts, schrumpfe links wenn Bedingung verletzt.
Visual
[2,1,5,1,3,2] k=3: window[0..2]=8→window[1..3]=7→window[2..4]=9→window[3..5]=6 → max=9
Common mistakes
- Variables Fenster: vergessen, den linken Zeiger vorzurücken wenn Bedingung verletzt ist.
- Fenstergröße k: Array muss mindestens k Elemente haben – Randfall prüfen.
Practice questions
- Längstes Teilstring ohne wiederholte Zeichen finden.
- Minimale Länge eines Teilarrays mit Summe ≥ S finden.
Space
O(1) oder O(k) je nach Anwendung