Running Sum of an Array

Q: Jaka jest suma bieżąca tablicy?

To druga tablica, w której każdy element jest sumą wszystkich elementów aż do tej samej pozycji w pierwszej tablicy włącznie. Nazywa się ją również sumą prefiksową lub sumą skumulowaną. Suma narastająca z [3, 1, 4, 1, 5] to [3, 4, 8, 9, 14] .

Q: Jaka jest złożoność czasowa obliczania sumy bieżącej?

Czas O(n) przy jednej sumie przenoszonej od lewej do prawej oraz dodatkowa pamięć O(1) poza wynikiem. Ponowne obliczanie każdego prefiksu od początku zajmuje O(n²) .

Q: Czy potrafisz obliczyć sumę narastającą w miejscu?

Tak. Przejdź od indeksu 1 do końca i ustaw nums[i] += nums[i-1] . Wtedy nums[i-1] zawiera już sumę wszystkich wcześniejszych elementów, więc każdy element będzie równy sumie prefiksowej. Oryginalne wartości zostaną utracone.

Q: Jak sumy prefiksowe pomagają w zapytaniach o sumę w zakresie?

Suma fragmentu nums[l..r] wynosi prefix[r] - prefix[l-1] albo prefix[r] , gdy l = 0 . W przypadku [3, 4, 8, 9, 14] suma elementów o indeksach od 2 do 4 wynosi 14 - 4 = 10 . Każde zapytanie zajmuje O(1) po jednym przejściu O(n) .

PoczątkującySumy prefiksowe

+10

Otrzymujesz tablicę liczb całkowitych nums. Zwróć nową tablicę o tej samej długości, której element na indeksie i jest równy nums[0] + nums[1] + ... + nums[i], czyli sumie pierwszych i+1 liczb.

Funkcja

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

numsinteger-array: liczby, które należy dodawać od lewej do prawej
Zwracainteger-array: sumy bieżące, po jednej dla każdego elementu tablicy nums

Ograniczenia

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Każda suma bieżąca mieści się w 32-bitowej liczbie całkowitej ze znakiem.

Przykłady

Wejście: nums = [3, 1, 4, 1, 5]
Wyjście: [3, 4, 8, 9, 14]
Wyjaśnienie: Dodawaj dalej: 3, potem 3 + 1 = 4, 4 + 4 = 8, 8 + 1 = 9 i 9 + 5 = 14. Każda suma trafia do indeksu ostatnio dodanej liczby.

Wejście: nums = [-2, 5, -3]
Wyjście: [-2, 3, 0]
Wyjaśnienie: Liczby ujemne obniżają sumę: -2, następnie -2 + 5 = 3, a potem 3 + (-3) = 0.

Wejście: nums = [7]
Wyjście: [7]
Wyjaśnienie: Pojedyncza liczba ma jedną sumę bieżącą — samą siebie, więc odpowiedzią jest [7].

Pytanie dodatkowe

Czy potrafisz zbudować to samo dla siatki, w której każda komórka zawiera sumę prostokąta od lewego górnego rogu do tej komórki?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Każda odpowiedź jest sumą prefiksu tablicy nums, a sąsiednie prefiksy różnią się jednym elementem. Ponowne obliczanie każdego prefiksu od początku powtarza niemal całą pracę. Zamiast tego przenoś dalej jedną sumę, a obliczenie każdej odpowiedzi będzie wymagało tylko jednego dodawania.

Dodaj kolejno każdy prefiks od początku

Intuicja

Postępuj zgodnie z definicją: dla każdego indeksu i zacznij od sumy równej 0, dodaj nums[0] do nums[i] i zapisz wynik. To poprawne, ponieważ każda odpowiedź jest obliczana dokładnie zgodnie z definicją.

Indeks i wymaga i+1 dodawań, więc tablica wymaga n(n+1)/2 dodawań: około 1.25 × 10^7 dodawań dla n = 5000, co powinno wystarczyć.

Algorytm

Utwórz tablicę wyników o długości n.
Dla każdego indeksu i ustaw total = 0.
Dodaj nums[j] do total dla każdego j od 0 do i.
Zapisz total pod indeksem i w tablicy wyników i zwróć tablicę wyników po ostatnim indeksie.

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

Obliczaj sumę bieżącą

Intuicja

Suma pierwszych i+1 liczb to suma pierwszych i liczb plus nums[i]: result[i] = result[i-1] + nums[i]. Nie musisz więc cofać się o więcej niż jeden krok, a wystarczy jedna zmienna total. Dla [3, 1, 4, 1, 5] otrzymujemy 3, 4, 8, 9, 14, co jest odpowiedzią.

Każdy element wymaga jednego dodawania: czas O(n) i O(1) dodatkowej przestrzeni poza odpowiedzią.

Algorytm

Utwórz tablicę odpowiedzi o długości n i ustaw total = 0.
Przejdź przez indeksy od lewej do prawej i dodawaj nums[i] do total.
Zapisz total pod indeksem i w tablicy odpowiedzi.
Zwróć tablicę odpowiedzi.

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

Pułapki i przypadki brzegowe

Resetowanie total wewnątrz pętli. Każda odpowiedź staje się samym nums[i], a [3, 1, 4] wraca bez zmian.
Odczyt result[i-1] przy i = 0. W większości języków wykracza to poza zakres; Python odczytuje ostatni element, więc wersja działająca w miejscu dodaje ostatnią liczbę do pierwszej.
Zatrzymanie wewnętrznej pętli metody brute force na j < i. Pomija ona nums[i], więc każda odpowiedź jest o jedną liczbę za krótka.
W R rozbudowywanie wyniku za pomocą result <- c(result, total) kopiuje wektor przy każdym kroku i sprawia, że szybkie podejście ma złożoność kwadratową. Najpierw zaalokuj wektor o pełnej długości.
W C zapomnienie o *returnSize = numsSize. Wtedy funkcja wywołująca nie wie, ile sum odczytać.

Najczęstsze pytania4

Jaka jest suma bieżąca tablicy?

To druga tablica, w której każdy element jest sumą wszystkich elementów aż do tej samej pozycji w pierwszej tablicy włącznie. Nazywa się ją również sumą prefiksową lub sumą skumulowaną. Suma narastająca z [3, 1, 4, 1, 5] to [3, 4, 8, 9, 14].

Jaka jest złożoność czasowa obliczania sumy bieżącej?

Czas O(n) przy jednej sumie przenoszonej od lewej do prawej oraz dodatkowa pamięć O(1) poza wynikiem. Ponowne obliczanie każdego prefiksu od początku zajmuje O(n²).

Czy potrafisz obliczyć sumę narastającą w miejscu?

Tak. Przejdź od indeksu 1 do końca i ustaw nums[i] += nums[i-1]. Wtedy nums[i-1] zawiera już sumę wszystkich wcześniejszych elementów, więc każdy element będzie równy sumie prefiksowej. Oryginalne wartości zostaną utracone.

Jak sumy prefiksowe pomagają w zapytaniach o sumę w zakresie?

Suma fragmentu nums[l..r] wynosi prefix[r] - prefix[l-1] albo prefix[r], gdy l = 0. W przypadku [3, 4, 8, 9, 14] suma elementów o indeksach od 2 do 4 wynosi 14 - 4 = 10. Każde zapytanie zajmuje O(1) po jednym przejściu O(n).

def runningSum(nums):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argument

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

Oczekiwany wynik

[3, 4, 8, 9, 14]