Contare i sottoarray con una somma obiettivo
Combinare somme prefisse e una hash map
Contare i sottoarray con una somma obiettivo è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 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.
Una domanda più difficile
Ora arriva la parte interessante: contare quanti sottoarray hanno somma pari a un valore k. Controllare ogni coppia è lento, ma le somme prefisse insieme a una mappa hash risolvono il problema. 🎯
Riformulare con i prefissi
La somma di un sottoarray è uguale a prefix[r + 1] meno prefix[l]. Quindi una somma pari a k significa che due valori di prefisso differiscono esattamente di k.
Il riarrangiamento fondamentale
Se il prefisso corrente è P, le serve un prefisso precedente uguale a P meno k. Questo riarrangiamento è l'intero trucco.
need = current_prefix - kConti, non cerchi
Invece di tornare indietro a ogni iterazione, memorizzi quante volte è comparso ogni valore di prefisso. Un conteggio progressivo fornisce la risposta in O(1).
Usi una mappa delle frequenze
Un dizionario associa a ogni valore di prefisso il numero di volte in cui è comparso. Questa mappa trasforma la ricerca in un conteggio immediato.
from collections import defaultdict
seen = defaultdict(int)Inizializzi il prefisso vuoto
Prima del ciclo, registri che il prefisso 0 è comparso una volta. Questo valore iniziale permette di contare i sottoarray che iniziano dall'indice 0.
seen[0] = 1Il ciclo in un'unica passata
Per ogni elemento, aggiorni il prefisso progressivo, aggiunga il conteggio del valore necessario e poi registri il prefisso corrente. Una sola passata è sufficiente.
total += x
count += seen[total - k]
seen[total] += 1Perché l'ordine è importante
Deve aggiornare la risposta prima di registrare il prefisso corrente. Altrimenti viene conteggiato anche un intervallo di lunghezza zero e il conteggio non è più corretto.
Il vantaggio in termini di velocità
Ogni elemento richiede un lavoro costante, quindi il conteggio completo viene eseguito in O(n). È molto più veloce della forza bruta O(n al quadrato) per input grandi.
Anche i numeri negativi vanno bene
A differenza delle finestre scorrevoli, questo metodo gestisce senza problemi i numeri negativi, perché le differenze tra prefissi restano valide indipendentemente dai segni.
Un caso d'uso classico
Questo schema risolve il famoso problema della somma del sottoarray uguale a k e molte varianti camuffate nei giudici di programmazione competitiva.
Verifica rapida
Il prefisso progressivo è P e l'obiettivo è k.
Riepilogo
Ora può contare i sottoarray con somma obiettivo in O(n), usando somme prefisse e una mappa delle frequenze. Inizializzi il prefisso 0, poi conti prima di registrare. ✅
Domande Frequenti
La lezione «Contare i sottoarray con una somma obiettivo» è gratuita?
Sì — il testo completo di «Contare i sottoarray con una somma obiettivo» è 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 «Contare i sottoarray con una somma obiettivo»?
Combinare somme prefisse e una hash map 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 3 di 4.
Quanto tempo richiede la lezione «Contare i sottoarray con una somma obiettivo»?
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