Contare i sottoarray con una somma obiettivo

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. 🎯

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.

Se il prefisso corrente è P, le serve un prefisso precedente uguale a P meno k. Questo riarrangiamento è l'intero trucco.

Invece di tornare indietro a ogni iterazione, memorizzi quante volte è comparso ogni valore di prefisso. Un conteggio progressivo fornisce la risposta in O(1).

Un dizionario associa a ogni valore di prefisso il numero di volte in cui è comparso. Questa mappa trasforma la ricerca in un conteggio immediato.

Prima del ciclo, registri che il prefisso 0 è comparso una volta. Questo valore iniziale permette di contare i sottoarray che iniziano dall'indice 0.

Per ogni elemento, aggiorni il prefisso progressivo, aggiunga il conteggio del valore necessario e poi registri il prefisso corrente. Una sola passata è sufficiente.

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.

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.

A differenza delle finestre scorrevoli, questo metodo gestisce senza problemi i numeri negativi, perché le differenze tra prefissi restano valide indipendentemente dai segni.

Questo schema risolve il famoso problema della somma del sottoarray uguale a k e molte varianti camuffate nei giudici di programmazione competitiva.

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. ✅