Running Sum of an Array

Q: Qual è la somma progressiva di un array?

È un secondo array in cui ogni elemento è il totale di tutto ciò che precede e include la stessa posizione nel primo array. È anche chiamato somma dei prefissi o somma cumulativa. La somma progressiva di [3, 1, 4, 1, 5] è [3, 4, 8, 9, 14] .

Q: Qual è la complessità temporale del calcolo di una somma cumulativa?

Tempo O(n) con un totale trasportato da sinistra a destra e spazio aggiuntivo O(1) , oltre alla risposta. Ricalcolare ogni prefisso dall'inizio richiede O(n²) .

Q: Riesci a calcolare la somma progressiva sul posto?

Sì. Procedi dall’indice 1 fino alla fine e imposta nums[i] += nums[i-1] . A quel punto nums[i-1] contiene già il totale di tutti gli elementi fino a lì, quindi ogni elemento finisce per contenere la propria somma prefissa. Perdi i valori originali.

Q: In che modo le somme prefisse aiutano con le query sulle somme di intervalli?

Il totale di una porzione nums[l..r] è prefix[r] - prefix[l-1] , oppure prefix[r] quando l = 0 . Con [3, 4, 8, 9, 14] , gli indici da 2 a 4 totalizzano 14 - 4 = 10 . Ogni query richiede O(1) dopo un'unica scansione O(n) .

PrincipianteSomme prefisse

+10

Ti viene fornito un array di interi nums. Restituisci un nuovo array della stessa lunghezza, il cui elemento all’indice i è nums[0] + nums[1] + ... + nums[i], la somma dei primi i+1 numeri.

Funzione

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

numsinteger-array: i numeri da sommare da sinistra a destra
Restituisceinteger-array: i totali progressivi, uno per ogni elemento di nums

Vincoli

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Ogni totale cumulativo rientra in un intero con segno a 32 bit.

Esempi

Input: nums = [3, 1, 4, 1, 5]
Output: [3, 4, 8, 9, 14]
Spiegazione: Continua ad aggiungere: 3, poi 3 + 1 = 4, 4 + 4 = 8, 8 + 1 = 9 e 9 + 5 = 14. Ogni totale va all’indice dell’ultimo numero aggiunto.

Input: nums = [-2, 5, -3]
Output: [-2, 3, 0]
Spiegazione: I numeri negativi abbassano il totale: -2, poi -2 + 5 = 3, poi 3 + (-3) = 0.

Input: nums = [7]
Output: [7]
Spiegazione: Un singolo numero ha un unico totale progressivo, se stesso, quindi la risposta è [7].

Per approfondire

Riesci a costruire la stessa cosa per una griglia, in cui ogni cella contiene il totale del rettangolo dall’angolo in alto a sinistra fino a quella cella?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Ogni risposta è la somma di un prefisso di nums e i prefissi vicini differiscono per un elemento. Ricalcolare ogni prefisso dall'inizio ripete quasi tutto il lavoro. Mantieni invece un totale progressivo: così ogni risposta richiede una sola addizione.

Somma ogni prefisso da zero

Intuizione

Segui la definizione: per ogni indice i, inizializza un totale a 0, aggiungi nums[0] fino a nums[i] e memorizzalo. È corretto perché ogni risposta viene calcolata esattamente come definito.

L’indice i richiede i+1 addizioni, quindi l’array richiede n(n+1)/2: circa 1.25 × 10^7 addizioni per n = 5000, dove 5000 sarebbe sufficiente.

Algoritmo

Crea un array di risposte di lunghezza n.
Per ogni indice i, imposta total = 0.
Aggiungi nums[j] a total per ogni j da 0 a i.
Memorizza total all'indice i della risposta e restituisci la risposta dopo l'ultimo indice.

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

Calcola un totale progressivo

Intuizione

La somma dei primi i+1 numeri è la somma dei primi i più nums[i]: result[i] = result[i-1] + nums[i]. Quindi non si torna mai indietro di più di un passaggio e basta una variabile total. Per [3, 1, 4, 1, 5] si ottengono 3, 4, 8, 9, 14, che è la risposta.

Ogni elemento richiede un'addizione: tempo O(n) e spazio extra O(1), oltre a quello necessario per la risposta.

Algoritmo

Crea un array di risposte di lunghezza n e imposta total = 0.
Procedi attraverso gli indici da sinistra a destra e aggiungi nums[i] a total.
Scrivi total all'indice i della risposta.
Restituisci la risposta.

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

Trappole e casi limite

Reimpostare total all'interno del ciclo. Ogni risposta diventa da sola nums[i] e [3, 1, 4] viene restituito invariato.
Leggere result[i-1] quando i = 0. La maggior parte dei linguaggi va fuori dai limiti; Python legge l'ultimo elemento, quindi una versione in place aggiunge l'ultimo numero al primo.
Interrompere il ciclo interno della forza bruta a j < i. In questo modo viene escluso nums[i], quindi ogni risposta contiene un numero in meno.
In R, aumentare la risposta con result <- c(result, total) copia il vettore a ogni passaggio e rende quadratica la soluzione veloce. Alloca prima l'intera lunghezza.
In C, dimenticare *returnSize = numsSize. Il chiamante non sa quindi quanti totali leggere.

Domande frequenti4

Qual è la somma progressiva di un array?

È un secondo array in cui ogni elemento è il totale di tutto ciò che precede e include la stessa posizione nel primo array. È anche chiamato somma dei prefissi o somma cumulativa. La somma progressiva di [3, 1, 4, 1, 5] è [3, 4, 8, 9, 14].

Qual è la complessità temporale del calcolo di una somma cumulativa?

Tempo O(n) con un totale trasportato da sinistra a destra e spazio aggiuntivo O(1), oltre alla risposta. Ricalcolare ogni prefisso dall'inizio richiede O(n²).

Riesci a calcolare la somma progressiva sul posto?

Sì. Procedi dall’indice 1 fino alla fine e imposta nums[i] += nums[i-1]. A quel punto nums[i-1] contiene già il totale di tutti gli elementi fino a lì, quindi ogni elemento finisce per contenere la propria somma prefissa. Perdi i valori originali.

In che modo le somme prefisse aiutano con le query sulle somme di intervalli?

Il totale di una porzione nums[l..r] è prefix[r] - prefix[l-1], oppure prefix[r] quando l = 0. Con [3, 4, 8, 9, 14], gli indici da 2 a 4 totalizzano 14 - 4 = 10. Ogni query richiede O(1) dopo un'unica scansione O(n).

def runningSum(nums):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

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

Output atteso

[3, 4, 8, 9, 14]