Somme su finestre di dimensione fissa
Far scorrere una finestra di lunghezza k in O(n)
Somme su finestre di dimensione fissa è 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
Molti problemi richiedono di calcolare la somma di ogni blocco di k elementi consecutivi. Ricalcolare ogni blocco da zero è inefficiente, ma è possibile fare di meglio. 🪟
Prima il metodo lento
L'idea ingenua consiste nel sommare separatamente ogni finestra di lunghezza k. Questo ripete il lavoro e ha un costo di O(n × k), troppo lento per input di grandi dimensioni.
for i in range(n - k + 1):
s = sum(a[i:i + k])L'idea chiave
Le finestre adiacenti si sovrappongono quasi completamente. Spostandosi di una posizione verso destra, è sufficiente rimuovere l'elemento più a sinistra e aggiungere un nuovo elemento a destra.
Inizializzare la prima finestra
Inizi calcolando una volta la somma dei primi k elementi. Questa singola somma sarà la base da aggiornare mentre la finestra scorre in avanti.
window = sum(a[:k])
best = windowSpostarsi di una posizione
Per spostare la finestra, aggiunga l'elemento che entra e sottragga quello che esce. In questo modo ogni passaggio richiede un lavoro costante O(1).
for i in range(k, n):
window += a[i] - a[i - k]Tenere traccia della risposta
Dopo ogni spostamento, aggiorni ciò che le serve, ad esempio la somma massima delle finestre incontrata finora. Il valore della finestra è sempre disponibile istantaneamente.
best = max(best, window)Il costo totale è lineare
Ogni elemento viene considerato per aggiungerlo e una seconda volta per rimuoverlo, quindi l'intera scansione è O(n). Questo è ampiamente sufficiente anche con vincoli di grandi dimensioni.
Attenzione agli indici
L'elemento che esce dalla finestra è a[i - k], non a[i - 1]. Gestire correttamente questo scarto è la soluzione al bug più comune nelle finestre di dimensione fissa.
Le medie vengono gratis
Le serve la media massima della finestra invece della somma? Divida semplicemente la somma memorizzata della finestra per k. La logica della finestra scorrevole non cambia affatto.
avg = window / kGestire gli array piccoli
Se l'array è più corto di k, non esiste alcuna finestra completa. Confronti in anticipo len(a) con k e restituisca subito il risultato, così da evitare un errore di indice.
if n < k:
return NoneQuando usare finestre fisse
Utilizzi questo schema quando la lunghezza è fissa e i valori possono essere combinati in modo economico, ad esempio per somme, conteggi o semplici statistiche progressive.
Verifica rapida
Fa scorrere una finestra di dimensione k di una posizione verso destra attraverso un array.
Riepilogo
Inizializzi una volta la prima finestra, poi aggiunga e sottragga a ogni passaggio per farla scorrere in O(1). L'intera scansione a dimensione fissa richiede tempo lineare. ✅
Domande Frequenti
La lezione «Somme su finestre di dimensione fissa» è gratuita?
Sì — il testo completo di «Somme su finestre di dimensione fissa» è 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 «Somme su finestre di dimensione fissa»?
Far scorrere una finestra di lunghezza k in O(n) 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 «Somme su finestre di dimensione fissa»?
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
- Somme su finestre di dimensione fissa
- Finestra variabile con due puntatori
- Sottostringa più lunga senza ripetizioni
- Contare le finestre che soddisfano una regola