Teilarrays mit einer Zielsummme zählen
Kombinieren Sie Präfixsummen mit einer Hashmap
Teilarrays mit einer Zielsummme zählen ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 3 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.
Eine schwierigere Frage
Jetzt kommt die Wendung: Zählen Sie, wie viele Teilarrays die Zielsumme k ergeben. Jedes Indexpaar zu prüfen ist langsam, aber Präfixsummen plus eine Hashmap lösen das Problem. 🎯
Mit Präfixsummen neu formuliert
Die Summe eines Teilarrays entspricht prefix[r + 1] minus prefix[l]. Eine Summe von k bedeutet also, dass sich zwei Präfixwerte genau um k unterscheiden.
Die entscheidende Umformung
Wenn das aktuelle Präfix P lautet, benötigen Sie ein früheres Präfix mit dem Wert P minus k. Diese Umformung ist der gesamte Trick.
need = current_prefix - kZählen statt suchen
Statt jedes Mal rückwärts zu suchen, merken Sie sich, wie oft jeder Präfixwert aufgetreten ist. Ein laufender Zähler liefert die Antwort in O(1).
Verwenden Sie eine Häufigkeits-Map
Ein Dictionary ordnet jedem Präfixwert zu, wie oft Sie ihn bisher gesehen haben. Diese Map macht aus der Suche eine sofortige Zählung.
from collections import defaultdict
seen = defaultdict(int)Initialisieren Sie das leere Präfix
Speichern Sie vor der Schleife, dass das Präfix 0 einmal aufgetreten ist. Diese Initialisierung sorgt dafür, dass Teilarrays ab Index 0 gezählt werden.
seen[0] = 1Die Schleife in einem Durchlauf
Aktualisieren Sie für jedes Element das laufende Präfix, addieren Sie die Anzahl des benötigten Werts und speichern Sie anschließend das aktuelle Präfix. Ein Durchlauf erledigt alles.
total += x
count += seen[total - k]
seen[total] += 1Warum die Reihenfolge wichtig ist
Sie müssen die Antwort erhöhen, bevor Sie das aktuelle Präfix speichern. Andernfalls wird ein Bereich der Länge null mitgezählt und die Zählung ist falsch.
Der Geschwindigkeitsvorteil
Jedes Element erfordert konstanten Aufwand, daher läuft die gesamte Zählung in O(n). Bei großen Eingaben ist das schneller als die Brute-Force-Lösung mit O(n zum Quadrat).
Negative Werte sind kein Problem
Im Gegensatz zu Sliding Windows funktioniert diese Methode auch mit negativen Zahlen, weil Präfixdifferenzen unabhängig von den Vorzeichen gültig bleiben.
Ein klassischer Anwendungsfall
Dieses Muster löst das bekannte Problem „subarray sum equals k“ und viele getarnte Varianten davon auf Wettbewerbsplattformen.
Kurzer Check
Ihr laufendes Präfix ist P und das Ziel ist k.
Zusammenfassung
Sie können Teilarrays mit einer bestimmten Summe in O(n) mithilfe von Präfixsummen und einer Häufigkeits-Map zählen. Initialisieren Sie Präfix 0 und zählen Sie, bevor Sie das aktuelle Präfix speichern. ✅
Häufig gestellte Fragen
Ist die Lektion „Teilarrays mit einer Zielsummme zählen“ kostenlos?
Ja — der vollständige Text von „Teilarrays mit einer Zielsummme zählen“ 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 „Teilarrays mit einer Zielsummme zählen“?
Kombinieren Sie Präfixsummen mit einer Hashmap 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 3 von 4.
Wie lange dauert die Lektion „Teilarrays mit einer Zielsummme zählen“?
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
- Ein Präfixsummen-Array erstellen
- Jeden Bereich durch Subtraktion summieren
- Teilarrays mit einer Zielsummme zählen
- Differenz-Arrays für Bereichsaktualisierungen