Summen in Fenstern fester Größe
Verschieben Sie ein Fenster der Länge k in O(n)
Summen in Fenstern fester Größe ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 1 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.
Das Problem wiederholter Summen
Bei vielen Aufgaben soll die Summe jedes Blocks aus k aufeinanderfolgenden Elementen berechnet werden. Jeden Block von Grund auf neu zu berechnen, ist unnötig aufwendig – das geht effizienter. 🪟
Zuerst der langsame Ansatz
Die naive Idee summiert jedes Fenster der Länge k einzeln. Dadurch wird Arbeit wiederholt und die Laufzeit beträgt O(n mal k), was bei großen Eingaben zu langsam ist.
for i in range(n - k + 1):
s = sum(a[i:i + k])Die entscheidende Erkenntnis
Benachbarte Fenster überlappen sich fast vollständig. Beim Verschieben um eine Position nach rechts wird nur das am weitesten links stehende Element entfernt und rechts ein neues Element hinzugefügt.
Das erste Fenster initialisieren
Beginnen Sie, indem Sie die ersten k Elemente einmal summieren. Diese eine Summe bildet die Grundlage, die Sie beim Weiterschieben des Fensters laufend aktualisieren.
window = sum(a[:k])
best = windowUm eine Position verschieben
Um das Fenster zu verschieben, addieren Sie das hinzukommende Element und subtrahieren das wegfallende. Dadurch bleibt der Aufwand pro Schritt konstant bei O(1).
for i in range(k, n):
window += a[i] - a[i - k]Das Ergebnis verfolgen
Aktualisieren Sie nach jeder Verschiebung, was Sie benötigen, beispielsweise die bisher gesehene maximale Fenstersumme. Der Fensterwert steht jederzeit sofort zur Verfügung.
best = max(best, window)Die Gesamtkosten sind linear
Jedes Element wird einmal zum Ergebnis addiert und ein weiteres Mal daraus entfernt, sodass der gesamte Durchlauf O(n) benötigt. Damit lassen sich große Eingabegrenzen problemlos bewältigen.
Achten Sie auf die Indizes
Das Element, das das Fenster verlässt, ist a[i - k], nicht a[i - 1]. Der richtige Offset ist der häufigste Fehler bei Fenstern fester Größe.
Durchschnitte gibt es gratis dazu
Benötigen Sie statt der Summe den maximalen Fenster-Durchschnitt? Teilen Sie einfach die gespeicherte Fenstersumme durch k. Die Logik des gleitenden Fensters ändert sich überhaupt nicht.
avg = window / kKleine Arrays behandeln
Ist das Array kürzer als k, existiert kein vollständiges Fenster. Prüfen Sie zu Beginn len(a) gegen k und geben Sie frühzeitig zurück, um einen Indexfehler zu vermeiden.
if n < k:
return NoneWann sich Fenster fester Größe eignen
Verwenden Sie dieses Muster, wenn die Fensterlänge fest ist und sich Werte effizient kombinieren lassen, etwa bei Summen, Zählungen oder einfachen laufenden Statistiken.
Kurzer Check
Sie verschieben ein Fenster der Größe k in einem Array Schritt für Schritt nach rechts.
Zusammenfassung
Initialisieren Sie das erste Fenster einmal und addieren und subtrahieren Sie bei jedem Schritt, um es mit O(1) weiterzuschieben. Der gesamte Durchlauf fester Fenstergröße läuft in linearer Zeit. ✅
Häufig gestellte Fragen
Ist die Lektion „Summen in Fenstern fester Größe“ kostenlos?
Ja — der vollständige Text von „Summen in Fenstern fester Größe“ 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 „Summen in Fenstern fester Größe“?
Verschieben Sie ein Fenster der Länge k in O(n) 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 1 von 4.
Wie lange dauert die Lektion „Summen in Fenstern fester Größe“?
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