Running Sum of an Array
Du erhältst ein Array aus Ganzzahlen nums. Gib ein neues Array derselben Länge zurück, dessen Element am Index i nums[0] + nums[1] + ... + nums[i] ist, also die Summe der ersten i+1 Zahlen.
Funktion
- 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-104 ≤ nums[i] ≤ 104- 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
- Addiere weiter:
3, dann3 + 1 = 4,4 + 4 = 8,8 + 1 = 9und9 + 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 senken die Summe:
-2, dann-2 + 5 = 3, dann3 + (-3) = 0.
- Eingabe
- nums = [7]
- Ausgabe
- [7]
- Erklärung
- Eine einzelne Zahl hat eine laufende Summe, die mit ihr selbst identisch ist, also lautet die Antwort
[7].
Weiterführende Frage
Kannst du dasselbe für ein Raster erstellen, in 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.
Wie hängt die Antwort am Index
imit der Antwort am Indexi-1zusammen?Die beiden Summen unterscheiden sich genau um eine Zahl,
nums[i]. Du musst nie wieder ein Präfix vom Anfang an aufsummieren.Behalte eine Variable
total. Gehenumsvon links nach rechts durch, addiere jede Zahl zutotalund schreibetotalan derselben Stelle in die Antwort.
Lösung
Jede Antwort ist die Summe eines Präfixes von nums, und benachbarte Präfixe unterscheiden sich um ein Element. Wenn du jedes Präfix von Anfang an neu berechnest, wiederholst du fast die gesamte Arbeit. Führe stattdessen eine laufende Summe weiter, dann erfordert jede Antwort nur eine Addition.
Jedes Präfix von Grund auf aufsummieren
Idee
Folge der Definition: Beginne für jeden Index i mit einer Summe von 0, addiere nums[0] bis nums[i] und speichere sie. Das ist korrekt, weil jede Antwort genau wie definiert berechnet wird.
Für Index i sind i+1 Additionen nötig, also kostet das Array n(n+1)/2: etwa 1.25 × 10^7 Additionen für n = 5000, wobei 5000 ausreichen würde.
Algorithmus
- Erstelle ein Antwort-Array der Länge
n. - Setze für jeden Index
itotal = 0. - Addiere
nums[j]zutotalfür jedesjvon0bisi. - Speichere
totalam Indexider 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 resultFühre eine laufende Summe
Idee
Die Summe der ersten i+1 Zahlen ist die Summe der ersten i plus nums[i]: result[i] = result[i-1] + nums[i]. Du musst also nie mehr als einen Schritt zurückblicken, und eine Variable total reicht aus. Für [3, 1, 4, 1, 5] ergibt sich 3, 4, 8, 9, 14 – das ist die Antwort.
Jedes Element erfordert eine Addition: Zeitaufwand O(n) und zusätzlicher Speicherplatz von O(1) neben dem Ergebnis.
Algorithmus
- Erstelle ein Antwortarray der Länge
nund setzetotal = 0. - Gehe die Indizes von links nach rechts durch und addiere
nums[i]zutotal. - Schreibe
totalan den Indexider 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
totalinnerhalb der Schleife zurücksetzen. Jede Antwort besteht dann nur ausnums[i], und[3, 1, 4]bleibt unverändert.result[i-1]beii = 0lesen. Die meisten Sprachen greifen dabei außerhalb des gültigen Bereichs zu; Python liest das letzte Element, sodass eine In-place-Version die letzte Zahl zur ersten addiert.- Die innere Schleife der Brute-Force-Methode bei
j < ibeenden. Dadurch wirdnums[i]ausgelassen, und jede Antwort enthält eine Zahl zu wenig. - In R wird der Vektor bei
result <- c(result, total)in jedem Schritt kopiert, wodurch der schnelle Ansatz quadratisch wird. Reserviere zuerst die vollständige Länge. - In C
*returnSize = numsSizevergessen. Der Aufrufer weiß dann nicht, wie viele Summen er lesen soll.
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 derselben 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 für die Berechnung einer laufenden Summe?
O(n) Laufzeit mit einer Gesamtsumme, die von links nach rechts mitgeführt wird, und O(1) zusätzlichem Speicherplatz neben dem Ergebnis. Jedes Präfix vom Anfang an neu zu berechnen, dauert O(n²).
Kannst du die laufende Summe direkt berechnen?
Ja. Gehe von Index 1 bis zum Ende und setze nums[i] += nums[i-1]. Zu diesem Zeitpunkt enthält nums[i-1] bereits die Summe aller Werte bis dahin, sodass jedes Element schließlich seiner Präfixsumme entspricht. Die ursprünglichen Werte gehen verloren.
Wie helfen Präfixsummen bei Bereichssummenabfragen?
Die Summe eines Teilarrays nums[l..r] ist prefix[r] - prefix[l-1] oder prefix[r], wenn l = 0. Bei [3, 4, 8, 9, 14] ergibt die Summe der Indizes 2 bis 4 14 - 4 = 10. Jede Abfrage benötigt nach einem Durchlauf von O(n) nur O(1).
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def runningSum(nums):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argument
nums = [3, 1, 4, 1, 5]
Erwartete Ausgabe
[3, 4, 8, 9, 14]