Creare un array delle somme prefisse
Precalcolare una volta i totali progressivi
Creare un array delle somme prefisse è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Il problema delle somme ripetute
Si immagini di dover rispondere a centinaia di domande sulle somme di intervalli dello stesso array. Calcolare ogni intervallo da zero è lento. Una somma prefissa risolve il problema. 🚀
Che cos'è una somma prefissa
Un array di somme prefisse memorizza, a ogni indice, il totale di tutti gli elementi fino a quel punto. Un'unica scansione di pre-calcolo trasforma somme lente in risposte immediate.
Un piccolo esempio
Per [3, 1, 4], i totali progressivi sono 3, poi 4 e infine 8. Questa lista crescente di totali è esattamente la somma prefissa.
La ricorrenza fondamentale
Ogni elemento è dato dal totale precedente più l'elemento corrente. Questa semplice ricorrenza è il cuore dell'intera tecnica.
prefix[i] = prefix[i - 1] + a[i]Costruirla nel codice
Si attraversa l'array una volta mantenendo un totale progressivo. A ogni passaggio si aggiunge la nuova somma, quindi la costruzione dell'array è un'unica scansione lineare.
prefix = [0]
for x in a:
prefix.append(prefix[-1] + x)Perché uno zero iniziale è utile
Iniziare prefix con uno zero iniziale significa che prefix[i] contiene la somma dei primi i elementi. In seguito, questo rende semplici i calcoli sugli intervalli.
Convenzione per gli indici
Con lo zero iniziale, prefix[k] è uguale a a[0] + ... + a[k-1]. Mantenere corretta questa convenzione evita difficili errori off-by-one.
Costo della costruzione
Per costruire l'array delle somme prefisse si tocca ogni elemento esattamente una volta, quindi il costo è O(n) in termini di tempo. Questo costo viene sostenuto una volta sola, dopodiché il risultato può essere riutilizzato.
Pre-calcolare una volta, interrogare spesso
Il grande vantaggio è il compromesso: si esegue una scansione lineare iniziale, così ogni successiva richiesta di somma diventa una rapida consultazione invece di un ciclo.
Una scorciatoia in stile Python
La libreria standard può costruire i totali al posto Suo. itertools.accumulate produce le somme progressive con un'unica chiamata ordinata.
from itertools import accumulate
prefix = [0] + list(accumulate(a))Attenzione alla memoria
L'array delle somme prefisse ha la stessa lunghezza dell'input più uno. Per input enormi, si ricordi che raddoppia l'uso della memoria.
Verifica rapida
Si costruisce un array di somme prefisse. Che cosa contiene di solito l'indice 0?
Riepilogo
Ha imparato a costruire un array di somme prefisse con un'unica scansione O(n), usando uno zero iniziale per semplificare gli indici. Si esegue il pre-calcolo una volta e poi si riutilizza il risultato. ✅
Domande Frequenti
La lezione «Creare un array delle somme prefisse» è gratuita?
Sì — il testo completo di «Creare un array delle somme prefisse» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Creare un array delle somme prefisse»?
Precalcolare una volta i totali progressivi Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Creare un array delle somme prefisse»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Creare un array delle somme prefisse
- Sommare qualsiasi intervallo con una sottrazione
- Contare i sottoarray con una somma obiettivo
- Array delle differenze per aggiornamenti su intervalli