Algorithmen und Datenstrukturen · Middle · Frage 57 von 75
Teilarray-Summe gleich k: warum speichert man Zählungen der Präfixsummen in einer Hash-Map?
- 1Um Präfixsummen gar nicht erst berechnen zu müssen
- 2Um die Präfixsummen für eine spätere binäre Suche zu sortieren
- 3Ein hier endendes Teilarray hat Summe k, wenn
prefix - kschon vorkam
Antwort zeigen
Richtige Antwort: Ein hier endendes Teilarray hat Summe k, wenn prefix - k schon vorkam
Erklärung
Die Summe von (i, j] ist prefix[j] - prefix[i]. Addiere für jede Position, wie viele frühere Präfixe prefix - k waren. Ein Durchlauf, O(n), und es funktioniert anders als ein Schiebefenster mit negativen Zahlen.