Running Sum of an Array

Q: Was ist die laufende Summe eines Arrays?

Es ist ein zweites Array, in dem jedes Element die Summe aller Elemente bis einschließlich der entsprechenden Position im ersten Array ist. Es wird auch Präfixsumme oder kumulative Summe genannt. Die laufende Summe von [3, 1, 4, 1, 5] ist [3, 4, 8, 9, 14] .

Q: Wie hoch ist die Zeitkomplexität der Berechnung einer laufenden Summe?

Mit einer Summe, die von links nach rechts mitgeführt wird, beträgt der Zeitaufwand O(n) , mit einer Addition pro Element, und der zusätzliche Speicherbedarf neben dem Ergebnis O(1) . Jedes Präfix von Anfang an neu zu berechnen, kostet n(n+1)/2 Additionen, also O(n²) .

Q: Kannst du die laufende Summe direkt berechnen?

Ja. Gehe von Index 1 bis zum Ende und setze nums[i] += nums[i-1] . Jedes Element enthält dann seine Präfixsumme, da nums[i-1] bereits in die Summe aller vorherigen Elemente umgewandelt wurde. Dabei wird kein weiteres Array außer der Eingabe verwendet, aber die ursprünglichen Werte werden überschrieben.

Q: Wie helfen Präfixsummen bei Bereichssummenabfragen?

Sobald du die laufenden Summen hast, ist die Summe eines beliebigen Teilbereichs nums[l..r] gleich prefix[r] - prefix[l-1] oder prefix[r] , wenn l = 0 . Bei den laufenden Summen [3, 4, 8, 9, 14] ergibt die Summe der Indizes 2 bis 4 14 - 4 = 10 . Nach einem einzigen Durchlauf mit O(n) benötigt jede Abfrage O(1) Zeit.

EinsteigerPräfixsummen

+10

Du erhältst ein Array aus ganzen Zahlen nums. Gib ein neues Array derselben Länge zurück, dessen Element am Index i nums[0] + nums[1] + ... + nums[i] ist, also die laufende Summe, nachdem die ersten i+1 Zahlen von links gelesen wurden.

Funktion

runningSum(nums: integer-array) → integer-array

numsinteger-array: die Zahlen von links nach rechts addieren
Gibt zurückinteger-array: die laufenden Summen, eine für jedes Element von nums

Einschränkungen

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Jede laufende Summe passt in eine vorzeichenbehaftete 32-Bit-Ganzzahl.

Beispiele

Eingabe: nums = [3, 1, 4, 1, 5]
Ausgabe: [3, 4, 8, 9, 14]
Erklärung: Weiter addieren: 3, dann 3 + 1 = 4, 4 + 4 = 8, 8 + 1 = 9 und 9 + 5 = 14. Jede Summe kommt an den Index der zuletzt addierten Zahl.

Eingabe: nums = [-2, 5, -3]
Ausgabe: [-2, 3, 0]
Erklärung: Negative Zahlen verringern die Summe: -2, dann -2 + 5 = 3, dann 3 + (-3) = 0.

Eingabe: nums = [7]
Ausgabe: [7]
Erklärung: Eine einzelne Zahl hat genau eine laufende Summe, nämlich sich selbst. Daher lautet die Antwort [7].

+13 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du dasselbe für ein Raster erstellen, bei dem jede Zelle die Summe des Rechtecks von der oberen linken Ecke bis zu dieser Zelle enthält?

Tipps

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

0 von 3 geöffnet

Lösung

Jede Antwort ist die Summe eines Präfixes von nums, und zwei benachbarte Präfixe unterscheiden sich um genau ein Element. Jedes Präfix von Anfang an neu zu berechnen, wiederholt fast die gesamte Arbeit, während das fortlaufende Mitführen einer Summe jede Antwort mit einer einzigen Addition liefert. Das Ergebnis ist das Präfixsummen-Array, die Grundlage für schnelle Bereichssummen.

Jedes Präfix von Grund auf aufsummieren

Idee

Folge der Definition Wort für Wort. Beginne für jeden Index i eine neue Summe bei 0, addiere nums[0] bis nums[i] und speichere das Ergebnis. Für [3, 1, 4, 1, 5] addiert die letzte Antwort alle fünf Zahlen: 3 + 1 + 4 + 1 + 5 = 14.

Das ist korrekt, wiederholt sich aber. Die Summe für Index 4 beginnt wieder bei nums[0], obwohl die Summe für Index 3, 9, bereits die Summe der ersten vier Zahlen enthält. Für Index i sind i+1 Additionen nötig, also kostet das gesamte Array 1 + 2 + ... + n = n(n+1)/2. Für n = 5000 sind das etwa 1.25 × 10^7 Additionen, obwohl 5000 genügen würden.

Abgesehen vom Ergebnisarray, das du ohnehin zurückgibst, speichert es nur eine Summe und zwei Indizes, daher beträgt der zusätzliche Speicherplatz O(1).

Algorithmus

Erstelle ein Antwortarray der Länge n.
Setze für jeden Index i total = 0.
Addiere nums[j] für jedes j von 0 bis i zu total.
Speichere total am Index i der Antwort und gib die Antwort nach dem letzten Index zurück.

def runningSum(nums):
    result = []
    for i in range(len(nums)):
        total = 0
        for j in range(i + 1):
            total += nums[j]
        result.append(total)
    return result

Führe eine laufende Summe

Idee

Die Summe der ersten i+1 Zahlen ist die Summe der ersten i Zahlen plus nums[i]: result[i] = result[i-1] + nums[i]. Du musst also nie mehr als einen Schritt zurückblicken. Verwende eine einzelne Variable total, addiere beim Lesen jede Zahl dazu und schreibe den neuen Wert in die Antwort.

Bei [3, 1, 4, 1, 5] nimmt total nacheinander die Werte 3, 4, 8, 9, 14 an, und diese fünf Werte sind die Antwort. Jedes Element wird einmal gelesen und erfordert eine Addition, also beträgt die Laufzeit O(n). Abgesehen vom Antwort-Array ist total der einzige Speicherbedarf, also beträgt der zusätzliche Speicherplatz O(1).

Keine Summe kann hier größer als 5000 × 10^4 = 5 × 10^7 werden, was in eine 32-Bit-Ganzzahl passt. Bei größeren Eingaben sind Präfixsummen ein klassischer Fall für einen Überlauf, und eine 64-Bit-Summe ist die sichere Standardwahl.

Algorithmus

Erstelle ein Antwort-Array der Länge n und setze total = 0.
Gehe die Indizes von links nach rechts durch und addiere nums[i] zu total.
Schreibe total an den Index i der Antwort.
Gib die Antwort zurück.

def runningSum(nums):
    result = []
    total = 0
    for num in nums:
        total += num
        result.append(total)
    return result

Stolperfallen und Grenzfälle

Die Schleife enthält nur eine Zeile mit echter Arbeit, daher beziehen sich die Fehler darauf, wo die Gesamtsumme gespeichert wird und wohin sie gelangt.

total innerhalb der Schleife zurücksetzen. Jedes Ergebnis wird dann allein zu nums[i], und [3, 1, 4] bleibt unverändert.
result[i] = result[i-1] + nums[i] verwenden, ohne i = 0 zu behandeln. Der Index -1 liegt in den meisten Sprachen außerhalb des gültigen Bereichs, und in Python bezeichnet er das letzte Element. Daher addiert eine In-place-Version, die bei 0 beginnt, die letzte Zahl zur ersten.
Die innere Schleife des ersten Ansatzes bei j < i beenden. Dadurch wird nums[i] ausgelassen, sodass jedes Ergebnis um eine Zahl zu niedrig ist.
Das Ergebnis durch Kopieren erweitern. In R kopiert result <- c(result, total) bei jedem Schritt den gesamten Vektor, wodurch der schnelle Ansatz wieder quadratisch wird. Reserviere zuerst Speicher für die vollständige Länge.
*returnSize = numsSize in C vergessen. Ohne diese Angabe weiß der Aufrufer nicht, wie viele Summen ausgelesen werden sollen.

Häufige Fragen4

Was ist die laufende Summe eines Arrays?

Es ist ein zweites Array, in dem jedes Element die Summe aller Elemente bis einschließlich der entsprechenden Position im ersten Array ist. Es wird auch Präfixsumme oder kumulative Summe genannt. Die laufende Summe von [3, 1, 4, 1, 5] ist [3, 4, 8, 9, 14].

Wie hoch ist die Zeitkomplexität der Berechnung einer laufenden Summe?

Mit einer Summe, die von links nach rechts mitgeführt wird, beträgt der Zeitaufwand O(n), mit einer Addition pro Element, und der zusätzliche Speicherbedarf neben dem Ergebnis O(1). Jedes Präfix von Anfang an neu zu berechnen, kostet n(n+1)/2 Additionen, also O(n²).

Kannst du die laufende Summe direkt berechnen?

Ja. Gehe von Index 1 bis zum Ende und setze nums[i] += nums[i-1]. Jedes Element enthält dann seine Präfixsumme, da nums[i-1] bereits in die Summe aller vorherigen Elemente umgewandelt wurde. Dabei wird kein weiteres Array außer der Eingabe verwendet, aber die ursprünglichen Werte werden überschrieben.

Wie helfen Präfixsummen bei Bereichssummenabfragen?

Sobald du die laufenden Summen hast, ist die Summe eines beliebigen Teilbereichs nums[l..r] gleich prefix[r] - prefix[l-1] oder prefix[r], wenn l = 0. Bei den laufenden Summen [3, 4, 8, 9, 14] ergibt die Summe der Indizes 2 bis 4 14 - 4 = 10. Nach einem einzigen Durchlauf mit O(n) benötigt jede Abfrage O(1) Zeit.

Python

def runningSum(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

nums = [3, 1, 4, 1, 5]

Erwartet

[3, 4, 8, 9, 14]