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 si trova fino alla stessa posizione inclusa nel primo array. È anche chiamata 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?

Con un totale riportato da sinistra a destra, il tempo è O(n) , con un’addizione per elemento, e lo spazio aggiuntivo è O(1) , oltre alla risposta. Ricalcolare ogni prefisso dall’inizio richiede n(n+1)/2 addizioni, ovvero O(n²) .

Q: Riesci a calcolare la somma cumulativa sul posto?

Sì. Scorri dall’indice 1 fino alla fine e imposta nums[i] += nums[i-1] . Ogni elemento conterrà quindi la sua somma prefissa, perché nums[i-1] è già stato trasformato nel totale di tutto ciò che lo precede. Questo non usa altri array oltre a quello di input, ma distrugge i valori originali.

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

Una volta calcolate le somme cumulative, il totale di qualsiasi intervallo nums[l..r] è prefix[r] - prefix[l-1] , oppure prefix[r] quando l = 0 . Con le somme cumulative [3, 4, 8, 9, 14] , gli indici da 2 a 4 totalizzano 14 - 4 = 10 . Ogni query richiede tempo O(1) dopo un'unica passata O(n) .

PrincipianteSomme prefisse

+10

Ti viene fornito un array di numeri interi nums. Restituisci un nuovo array della stessa lunghezza, il cui elemento all'indice i è nums[0] + nums[1] + ... + nums[i], ovvero il totale progressivo dopo aver letto i primi i+1 numeri da sinistra.

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 progressivo 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, cioè se stesso, quindi la risposta è [7].

+13 test nascosti all’invio

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 due prefissi vicini differiscono per un solo elemento. Ricalcolare ogni prefisso dall'inizio ripete quasi tutto il lavoro, mentre mantenere un totale aggiornato permette di ottenere ogni risposta con una sola addizione. Il risultato è l'array delle somme dei prefissi, lo strumento alla base delle somme rapide su intervalli.

Somma ogni prefisso da zero

Intuizione

Segui la definizione alla lettera. Per ogni indice i, parti da un nuovo totale pari a 0, aggiungi nums[0] fino a nums[i] e memorizza il risultato. Per [3, 1, 4, 1, 5], l'ultima risposta somma tutti e cinque i numeri: 3 + 1 + 4 + 1 + 5 = 14.

È corretto, ma ripete il lavoro. Il totale per l'indice 4 riparte da nums[0], anche se il totale per l'indice 3, 9, contiene già la somma dei primi quattro numeri. L'indice i richiede i+1 addizioni, quindi l'intero array ne richiede 1 + 2 + ... + n = n(n+1)/2. Per n = 5000 sono circa 1.25 × 10^7 addizioni, quando ne basterebbero 5000.

A parte l'array dei risultati, che restituisci comunque, conserva solo un totale e due indici, quindi lo spazio aggiuntivo è O(1).

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 numeri più nums[i]: result[i] = result[i-1] + nums[i]. Quindi non guardi mai indietro di più di un passaggio. Mantieni una sola variabile total, aggiungi ogni numero man mano che lo leggi e scrivi il nuovo valore nella risposta.

Per [3, 1, 4, 1, 5], total assume i valori 3, 4, 8, 9, 14, e questi cinque valori costituiscono la risposta. Ogni elemento viene letto una volta e richiede un'addizione, quindi il tempo è O(n). Oltre all'array della risposta, l'unica memoria utilizzata è total, quindi lo spazio aggiuntivo è O(1).

Nessun totale può superare 5000 × 10^4 = 5 × 10^7, quindi rientra in un intero a 32 bit. Con input più grandi, le somme prefisse sono un classico caso in cui si verifica un overflow, e un totale a 64 bit è la scelta sicura predefinita.

Algoritmo

Crea un array di risposte di lunghezza n e imposta total = 0.
Scorri gli indici da sinistra a destra e aggiungi nums[i] a total.
Scrivi total nell'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

Il ciclo ha una sola riga di lavoro effettivo, quindi gli errori riguardano dove si trova il totale e dove viene trasferito.

Reimpostare total all'interno del ciclo. Ogni risposta diventa solo nums[i] e [3, 1, 4] viene restituito invariato.
Usare result[i] = result[i-1] + nums[i] senza gestire i = 0. L'indice -1 è fuori dai limiti nella maggior parte dei linguaggi e, in Python, corrisponde all'ultimo elemento, quindi una versione in place che inizia da 0 aggiunge il numero finale al primo.
Interrompere il ciclo interno del primo approccio a j < i. Esclude nums[i], quindi ogni risposta è più corta di un numero.
Far crescere la risposta copiandola. In R, result <- c(result, total) copia l'intero vettore a ogni passaggio, rendendo di nuovo quadratico l'approccio veloce. Alloca prima la lunghezza completa.
Dimenticare *returnSize = numsSize in C. Senza, il chiamante non sa 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 si trova fino alla stessa posizione inclusa nel primo array. È anche chiamata 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?

Con un totale riportato da sinistra a destra, il tempo è O(n), con un’addizione per elemento, e lo spazio aggiuntivo è O(1), oltre alla risposta. Ricalcolare ogni prefisso dall’inizio richiede n(n+1)/2 addizioni, ovvero O(n²).

Riesci a calcolare la somma cumulativa sul posto?

Sì. Scorri dall’indice 1 fino alla fine e imposta nums[i] += nums[i-1]. Ogni elemento conterrà quindi la sua somma prefissa, perché nums[i-1] è già stato trasformato nel totale di tutto ciò che lo precede. Questo non usa altri array oltre a quello di input, ma distrugge i valori originali.

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

Una volta calcolate le somme cumulative, il totale di qualsiasi intervallo nums[l..r] è prefix[r] - prefix[l-1], oppure prefix[r] quando l = 0. Con le somme cumulative [3, 4, 8, 9, 14], gli indici da 2 a 4 totalizzano 14 - 4 = 10. Ogni query richiede tempo O(1) dopo un'unica passata O(n).

Python

def runningSum(nums):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

[3, 4, 8, 9, 14]