Subarray Sum Equals K

+10

Du erhältst ein Array aus ganzen Zahlen nums und eine ganze Zahl k. Zähle die Teilarrays, deren Elemente sich genau zu k addieren. Ein Teilarray ist eine Folge aus einem oder mehreren benachbarten Elementen. Zwei Teilarrays zählen separat, wenn sie an unterschiedlichen Positionen beginnen oder enden, selbst wenn sie dieselben Werte enthalten. Die Werte können negativ oder null sein.

Funktion

subarraySum(nums: integer-array, k: integer) → integer

numsinteger-array: das Array aus ganzen Zahlen, das negative Werte und Nullen enthalten kann
kinteger: die Summe, die ein Teilarray erreichen muss, um gezählt zu werden
Gibt zurückinteger: die Anzahl der Teilarrays, deren Elemente zusammen k ergeben

Einschränkungen

1 ≤ nums.length ≤ 2 × 10⁴
-1000 ≤ nums[i] ≤ 1000
-10⁷ ≤ k ≤ 10⁷
Ein Array dieser Länge hat höchstens 200,010,000 Teilarrays, daher passt das Ergebnis in eine vorzeichenbehaftete 32-Bit-Ganzzahl.

Beispiele

Eingabe: nums = [3, 4, -7, 1, 3, 3, 1, -4]k = 7
Ausgabe: 4
Erklärung: Vier Folgen ergeben zusammen 7: [3, 4], [1, 3, 3], [3, 3, 1] und [3, 4, -7, 1, 3, 3]. In der letzten Folge heben die -7 die 3 und die 4 auf, und die Summe steigt später wieder auf 7, sodass eine Folge auch dann passen kann, wenn ihre Summe bereits über k gestiegen ist.

Eingabe: nums = [1, -1, 0]k = 0
Ausgabe: 3
Erklärung: Drei Teilarrays ergeben zusammen 0: [1, -1], [0] und das gesamte Array [1, -1, 0]. Die Folge [-1, 0] ergibt zusammen -1 und zählt daher nicht.

Eingabe: nums = [2, 2, 2]k = 4
Ausgabe: 2
Erklärung: Die Folge [2, 2] an den Indizes 0 und 1 und die Folge [2, 2] an den Indizes 1 und 2 enthalten dieselben Werte, befinden sich aber an unterschiedlichen Positionen, daher zählen beide. Das gesamte Array ergibt 6.

+17 versteckte Tests beim Einreichen

Weiterführende Frage

Wie würdest du die Lösung so ändern, dass sie die Länge des längsten Teilarrays zurückgibt, dessen Summe k ergibt, und weiterhin in O(n) Zeit läuft?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Ein Array aus n Zahlen hat n(n+1)/2 Teilarrays, also etwa 2 × 10^8, wenn n = 2 × 10^4 ist. Daher dauert es zu lange, jedes einzelne zu addieren. Die negativen Werte schließen auch ein Sliding Window aus: Die Summe eines Fensters kann fallen und wieder steigen, sodass es keine Regel gibt, die dir sagt, wann du es verkleinern sollst. Die Idee, die das Problem knackt, besteht darin, jede Teilarraysumme als Differenz zweier Präfixsummen zu schreiben. Teilarrays zu zählen, die am aktuellen Element enden und zusammen k ergeben, bedeutet dann, frühere Präfixsummen zu zählen, die der aktuellen Präfixsumme minus k entsprechen. Eine Hash-Map kann das in einem Durchlauf erledigen.

Jeder Durchlauf mit einer laufenden Summe

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Jedes Teilarray hat einen ersten Index start und einen letzten Index end. Wenn du jedes Paar durchgehst und seine Summe überprüfst, erfasst du jedes Teilarray genau einmal, also stimmt die Anzahl.

Du brauchst keine dritte Schleife, um jedes Teilarray aufzusummieren. Fixiere start, bewege dann end Schritt für Schritt nach rechts und addiere nums[end] zu einer laufenden total. Die Summe enthält immer die Summe der Elemente von start bis end, daher kostet jedes Teilarray eine Addition und einen Vergleich.

Hör nicht auf, wenn die Summe k erreicht oder überschreitet. Ein späterer negativer Wert kann sie wieder senken: Im ersten Beispiel verläuft die Summe ab Index 0 über 3, 7, 0, 1, 4, 7, sodass dieser Startindex bei Index 5 einen zweiten Treffer hat.

Der Aufwand entspricht der Anzahl der Paare. Bei n = 2 × 10^4 gibt es etwa 2 × 10^8 davon – für C ist das in Ordnung, für Python, Ruby oder R aber viel zu langsam.

Algorithmus

Setze count auf 0.
Setze für jedes start von 0 bis n-1 total auf 0.
Addiere für jedes end von start bis n-1 nums[end] zu total.
Wenn total gleich k ist, addiere 1 zu count und fahre in jedem Fall fort.
Gib count zurück.

def subarraySum(nums, k):
    n = len(nums)
    count = 0
    for start in range(n):
        total = 0
        # Grow the subarray that begins at start, one element at a time
        for end in range(start, n):
            total += nums[end]
            if total == k:
                count += 1
    return count

Präfixsummen mit einer Häufigkeitskarte

Idee

Sei prefix[j] die Summe der ersten j Elemente, wobei für das leere Präfix prefix[0] = 0 gilt. Die Teilliste von Index i bis Index j-1 hat die Summe prefix[j] - prefix[i]. Eine Teilliste, die beim aktuellen Element endet, hat also genau dann die Summe k, wenn eine frühere Präfixsumme gleich der aktuellen Präfixsumme minus k ist. Jede solche frühere Präfixsumme markiert den Anfang einer passenden Teilliste.

Durchlaufe das Array einmal. Behalte die laufende Präfixsumme und eine Hash-Map seen, die jeder Präfixsumme angibt, wie oft sie bereits aufgetreten ist. Addiere bei jedem Element zuerst seen[prefix - k] zum Zähler und speichere anschließend das aktuelle Präfix. Die Suche vor dem Speichern verhindert, dass eine Teilliste leer ist: Bei k = 0 würde das zuerst erfolgende Speichern die aktuelle Präfixsumme mit sich selbst abgleichen.

Nimm das erste Beispiel mit k = 7. Die Präfixsummen sind 0, 3, 7, 0, 1, 4, 7, 8, 4. Wenn die Präfixsumme nach Index 1 den Wert 7 erreicht, enthält die Map eine 0, was [3, 4] ergibt. Wenn sie nach Index 5 erneut 7 erreicht, enthält die Map zwei Nullen, das leere Präfix und das Präfix nach der -7; diese ergeben gleichzeitig [3, 4, -7, 1, 3, 3] und [1, 3, 3]. Bei 8 nach Index 6 enthält die Map eine 1, was [3, 3, 1] ergibt. Das macht insgesamt 4.

Dass die Map mit 0 beginnt, die einmal gesehen wurde, sorgt dafür, dass Teillisten gezählt werden, die bei Index 0 beginnen. Eine Zähl-Map statt einer Menge ist wichtig, weil dieselbe Präfixsumme mehrfach auftreten kann und jede Kopie eine andere Teilliste beginnt. Für jedes Element ist eine Suche und eine Aktualisierung nötig, daher beträgt die Laufzeit O(n), und die Map enthält höchstens n+1 Schlüssel.

Algorithmus

Erstelle eine Map seen mit seen[0] = 1 und setze prefix und count auf 0.
Addiere jedes Element zu prefix.
Addiere seen[prefix - k] zu count, wobei ein fehlender Schlüssel als 0 gelesen wird.
Addiere 1 zu seen[prefix].
Gib count zurück.

def subarraySum(nums, k):
    # seen[p] = how many prefixes so far add up to p; the empty prefix adds up to 0
    seen = {0: 1}
    prefix = 0
    count = 0
    for num in nums:
        prefix += num
        # Each earlier prefix equal to prefix - k starts a subarray that ends here and sums to k
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

Stolperfallen und Grenzfälle

Die meisten falschen Antworten entstehen, wenn du die Eingabe so behandelst, als wären alle Werte positiv, oder wenn du die Reihenfolge der beiden Map-Operationen vertauschst.

Ein Sliding Window, das verkleinert wird, sobald die Summe k überschreitet, funktioniert bei negativen Werten nicht. Beim ersten Beispiel liefert es 2 statt 4: Das Fenster behält seinen linken Rand bei Index 0, bis die Summe bei Index 6 den Wert 7 überschreitet, und versucht daher nie [1, 3, 3] oder [3, 3, 1].
Wenn du seen[0] = 1 weglässt, werden alle Teilarrays übersehen, die bei Index 0 beginnen. Für nums = [5] und k = 5 liefert es 0 statt 1.
Wenn du das aktuelle Präfix vor der Suche speicherst, werden leere Teilarrays mitgezählt, wenn k 0 ist. Für [1, -1, 0] liefert es 6 statt 3.
Ein Set von Präfixsummen anstelle einer Map mit Zählwerten zählt Wiederholungen zu selten. Für [0, 0, 0] und k = 0 ist die Antwort 6, weil jede frühere Kopie derselben Präfixsumme ein anderes Teilarray beginnen lässt.
Beim Brute-Force-Verfahren ist es aus demselben Grund wie beim Sliding Window falsch, die innere Schleife abzubrechen, wenn die Summe k überschreitet.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Subarray Sum Equals K?

Die Präfixsumme-und-Hashmap-Lösung benötigt O(n) Zeit und O(n) zusätzlichen Speicherplatz: einen Durchlauf mit einer Suche und einer Aktualisierung pro Element. Jedes Teilarray mit einer laufenden Summe zu überprüfen, benötigt O(n²) Zeit, und jedes Teilarray von Grund auf neu aufzusummieren, benötigt O(n³).

Warum funktioniert ein gleitendes Fenster bei „Subarray Sum Equals K“ nicht?

Ein Sliding Window beruht darauf, dass die Summe steigt, wenn das Fenster größer wird, und sinkt, wenn es kleiner wird. Das gilt nur, wenn alle Werte positiv sind. Bei negativen Werten kann ein Fenster, dessen Summe bereits zu groß ist, nach weiterem Vergrößern trotzdem noch passen. Daher gibt es keine Regel, die dir sagt, wann du die linke Grenze verschieben sollst. Wenn alle Werte positiv wären, ließe sich das Problem mit einem Sliding Window in O(n) Zeit und O(1) Speicher lösen.

Warum beginnt die Hash-Map mit der Zuordnung von 0 zu 1?

Dieser Eintrag steht für das leere Präfix vor dem ersten Element, dessen Summe 0 beträgt. Die Summe eines Teilarrays, das bei Index 0 beginnt, ergibt sich aus der aktuellen Präfixsumme minus diesem leeren Präfix. Ohne den Eintrag werden diese Teilarrays also nie gezählt. Für nums = [5] und k = 5 findet die Suche nach 5 - 5 = 0 diesen Eintrag und gibt 1 zurück.

Kann „Subarray Sum Equals K“ mit O(1) zusätzlichem Speicherplatz gelöst werden?

Nicht mit der Methode in einem Durchgang. Um die Übereinstimmungen zu zählen, die an einem Element enden, musst du wissen, welche Präfixsummen davor aufgetreten sind, und davon kann es bis zu n+1 verschiedene geben. Ohne die Map bleibt dir nur die laufende Summe in O(n²). Wenn alle Werte positiv sind, zählt ein gleitendes Fenster die Teilarrays in O(n) Zeit und O(1) Speicherplatz.

Python

def subarraySum(nums, k):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

nums = [3, 4, -7, 1, 3, 3, 1, -4]
k = 7

Erwartet