Variables Fenster mit zwei Zeigern
Vergrößern und verkleinern Sie das Fenster, bis eine Bedingung erfüllt ist
Variables Fenster mit zwei Zeigern ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Wenn das Fenster sich bewegt
Bei manchen Problemen ist die Fensterlänge nicht festgelegt. Stattdessen vergrößert und verkleinert sich das Fenster, damit eine Bedingung erfüllt bleibt, etwa dass eine Summe unter einem Grenzwert liegt.
Zwei Zeiger, ein Fenster
Verwenden Sie zwei Indizes, left und right, die die Fensterränder markieren. Der rechte Zeiger erweitert das Fenster, während left bei Bedarf folgt und es verkleinert.
left = 0
window = 0Nach rechts erweitern
Gehen Sie über jedes Element nach rechts und nehmen Sie es in das Fenster auf. Aktualisieren Sie dabei den laufenden Zustand, beispielsweise indem Sie den neuen Wert zu einer Summe addieren.
for right in range(n):
window += a[right]Bei Bedarf verkleinern
Solange das Fenster die Regel verletzt, verschieben Sie left nach rechts und entfernen dieses Element. So wird die Bedingung wiederhergestellt, ohne zurückzugehen.
while window > limit:
window -= a[left]
left += 1Das gültige Fenster ablesen
Nach Ende der inneren Schleife ist das Fenster von left bis right gültig. Seine Länge beträgt right minus left plus eins und kann direkt verwendet werden.
length = right - left + 1Das beste Ergebnis speichern
Aktualisieren Sie Ihr Ergebnis mit diesem gültigen Fenster, häufig mit dem bisher längsten. Tun Sie dies bei jeder Iteration, damit kein Fenster übersehen wird.
best = max(best, right - left + 1)Warum die Laufzeit linear ist
Jeder Zeiger bewegt sich nur vorwärts, niemals zurück. left und right legen zusammen höchstens n Schritte zurück, daher beträgt die Laufzeit des gesamten Durchlaufs O(n).
Die Monotoniebedingung
Das funktioniert, wenn das Erweitern des Fensters die Bedingung nur schwieriger erfüllbar macht. Dieses monotone Verhalten ermöglicht es, left niemals zurückzusetzen.
Längstes oder kürzestes Fenster
Für das kürzeste gültige Fenster verkleinern Sie es, solange die Regel noch gilt, und speichern das Ergebnis, bevor Sie abbrechen. Die Zeigermechanik bleibt gleich.
while window >= target:
best = min(best, right - left + 1)
window -= a[left]
left += 1Leere Fenster vermeiden
Wenn das Verkleinern das Fenster leeren kann, sichern Sie sich gegen ein Überholen von left durch right ab. Prüfen Sie außerdem, ob tatsächlich ein Ergebnis gefunden wurde, bevor Sie es zurückgeben.
Das Muster erkennen
Verwenden Sie ein variables Fenster, wenn eine Aufgabe nach einem längsten oder kürzesten zusammenhängenden Abschnitt fragt, der eine Bedingung für seine Elemente erfüllt.
Kurzer Check
Sie durchlaufen ein variables Fenster mit zwei Zeigern über ein Array der Größe n.
Zusammenfassung
Erweitern Sie right, um Elemente aufzunehmen, und verkleinern Sie das Fenster mit left, solange die Regel verletzt ist. Speichern Sie jedes gültige Fenster. Zeiger, die sich nur vorwärts bewegen, halten die Laufzeit bei O(n). ✅
Häufig gestellte Fragen
Ist die Lektion „Variables Fenster mit zwei Zeigern“ kostenlos?
Ja — der vollständige Text von „Variables Fenster mit zwei Zeigern“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Variables Fenster mit zwei Zeigern“?
Vergrößern und verkleinern Sie das Fenster, bis eine Bedingung erfüllt ist Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Variables Fenster mit zwei Zeigern“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Summen in Fenstern fester Größe
- Variables Fenster mit zwei Zeigern
- Längster Teilstring ohne Wiederholungen
- Fenster zählen, die eine Regel erfüllen