Running Sum of an Array

Q: Jaka jest suma skumulowana 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 tablicy [3, 1, 4, 1, 5] to [3, 4, 8, 9, 14] .

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

Przy jednej łącznej sumie przenoszonej od lewej do prawej złożoność czasowa wynosi O(n) — jedno dodawanie na element — a dodatkowa pamięć poza wynikiem to O(1) . Ponowne obliczanie każdego prefiksu od początku wymaga n(n+1)/2 dodawań, czyli 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] . Każdy element będzie wtedy zawierał swoją sumę prefiksową, ponieważ nums[i-1] został już zamieniony na sumę wszystkich poprzedzających go elementów. Nie wymaga to użycia żadnej tablicy poza wejściową, ale niszczy oryginalne wartości.

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

Gdy masz już sumy narastające, suma dowolnego fragmentu nums[l..r] wynosi prefix[r] - prefix[l-1] lub prefix[r] , gdy l = 0 . Przy sumach narastających [3, 4, 8, 9, 14] wartości od indeksu 2 do 4 sumują się do 14 - 4 = 10 . Każde zapytanie zajmuje O(1) czasu po jednym przebiegu O(n) .

PoczątkującySumy prefiksowe

+10

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

Funkcja

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

numsinteger-array: liczby do dodania 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].

+13 ukrytych testów przy wysłaniu

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ą pewnego prefiksu nums, a dwa sąsiednie prefiksy różnią się dokładnie jednym elementem. Ponowne obliczanie każdego prefiksu od początku powtarza prawie całą pracę, natomiast przenoszenie jednej sumy dalej pozwala uzyskać każdą odpowiedź za pomocą jednego dodawania. Wynikiem jest tablica sum prefiksowych — narzędzie umożliwiające szybkie obliczanie sum z przedziałów.

Zsumuj każdy prefiks od początku

Intuicja

Postępuj zgodnie z definicją słowo w słowo. Dla każdego indeksu i zacznij od nowa od sumy równej 0, dodaj nums[0] do nums[i] i zapisz wynik. Dla [3, 1, 4, 1, 5] ostatnia odpowiedź sumuje wszystkie pięć liczb: 3 + 1 + 4 + 1 + 5 = 14.

To poprawne rozwiązanie, ale powtarza te same obliczenia. Suma dla indeksu 4 jest obliczana od nowa od nums[0], mimo że suma dla indeksu 3, 9, zawiera już sumę pierwszych czterech liczb. Dla indeksu i potrzeba i+1 dodawań, więc dla całej tablicy potrzeba 1 + 2 + ... + n = n(n+1)/2 dodawań. Dla n = 5000 to około 1.25 × 10^7 dodawań, podczas gdy wystarczyłoby 5000.

Poza tablicą odpowiedzi, którą i tak zwracasz, rozwiązanie przechowuje tylko sumę i dwa indeksy, więc dodatkowe zużycie pamięci wynosi O(1).

Algorytm

Utwórz tablicę odpowiedzi 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 odpowiedzi i zwróć odpowiedź 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

Prowadź sumę narastającą

Intuicja

Suma pierwszych i+1 liczb to suma pierwszych i liczb plus nums[i]: result[i] = result[i-1] + nums[i]. Dzięki temu nigdy nie cofasz się o więcej niż jeden krok. Przechowuj jedną zmienną total, dodawaj do niej każdą liczbę podczas jej odczytywania i zapisuj nową wartość w tablicy wynikowej.

Dla [3, 1, 4, 1, 5] wartość total przyjmuje kolejno 3, 4, 8, 9, 14, a te pięć wartości stanowi wynik. Każdy element jest odczytywany raz i wymaga jednego dodawania, więc złożoność czasowa wynosi O(n). Poza tablicą wynikową jedynym używanym miejscem w pamięci jest total, więc dodatkowa złożoność pamięciowa wynosi O(1).

Żadna suma w tym zadaniu nie przekroczy wartości 5000 × 10^4 = 5 × 10^7, co mieści się w 32-bitowej liczbie całkowitej. Przy większych danych sumy prefiksowe to klasyczny przypadek, w którym może wystąpić przepełnienie, dlatego 64-bitowa zmienna przechowująca sumę jest bezpiecznym domyślnym wyborem.

Algorytm

Utwórz tablicę odpowiedzi o długości n i ustaw total = 0.
Przejdź przez indeksy od lewej do prawej i dodaj 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

Pętla wykonuje tylko jedną linię właściwej pracy, więc błędy dotyczą tego, gdzie przechowywana jest suma i dokąd trafia.

Resetowanie total wewnątrz pętli. Każda odpowiedź staje się samym nums[i], a [3, 1, 4] wraca bez zmian.
Używanie result[i] = result[i-1] + nums[i] bez obsługi i = 0. Indeks -1 jest poza zakresem w większości języków, a w Pythonie oznacza ostatni element, więc wersja działająca w miejscu, która zaczyna od 0, dodaje ostatnią liczbę do pierwszej.
Zatrzymanie pętli wewnętrznej w pierwszym podejściu na j < i. Pomija to nums[i], więc każda odpowiedź jest o jedną liczbę za mała.
Powiększanie wyniku przez kopiowanie. W R result <- c(result, total) kopiuje cały wektor przy każdym kroku, przez co szybkie podejście znów ma złożoność kwadratową. Najpierw zaalokuj tablicę o pełnej długości.
Zapomnienie o *returnSize = numsSize w C. Bez tego wywołujący nie wie, ile sum odczytać.

Najczęstsze pytania4

Jaka jest suma skumulowana 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 tablicy [3, 1, 4, 1, 5] to [3, 4, 8, 9, 14].

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

Przy jednej łącznej sumie przenoszonej od lewej do prawej złożoność czasowa wynosi O(n) — jedno dodawanie na element — a dodatkowa pamięć poza wynikiem to O(1). Ponowne obliczanie każdego prefiksu od początku wymaga n(n+1)/2 dodawań, czyli 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]. Każdy element będzie wtedy zawierał swoją sumę prefiksową, ponieważ nums[i-1] został już zamieniony na sumę wszystkich poprzedzających go elementów. Nie wymaga to użycia żadnej tablicy poza wejściową, ale niszczy oryginalne wartości.

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

Gdy masz już sumy narastające, suma dowolnego fragmentu nums[l..r] wynosi prefix[r] - prefix[l-1] lub prefix[r], gdy l = 0. Przy sumach narastających [3, 4, 8, 9, 14] wartości od indeksu 2 do 4 sumują się do 14 - 4 = 10. Każde zapytanie zajmuje O(1) czasu po jednym przebiegu O(n).

Python

def runningSum(nums):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

[3, 4, 8, 9, 14]