Subarray Sum Equals K

+10

Ti viene fornito un array di interi nums e un intero k. Conta i sottoarray i cui elementi sommati danno esattamente k. Un sottoarray è una sequenza di uno o più elementi adiacenti. Due sottoarray si contano separatamente quando iniziano o terminano in posizioni diverse, anche se contengono gli stessi valori. I valori possono essere negativi o zero.

Funzione

subarraySum(nums: integer-array, k: integer) → integer

numsinteger-array: l'array di numeri interi, che può contenere valori negativi e zeri
kinteger: la somma che un sottarray deve raggiungere per essere conteggiato
Restituisceinteger: il numero di sottoarray i cui elementi sommano a k

Vincoli

1 ≤ nums.length ≤ 2 × 10⁴
-1000 ≤ nums[i] ≤ 1000
-10⁷ ≤ k ≤ 10⁷
Un array di questa lunghezza ha al massimo 200,010,000 sottoarray, quindi il risultato rientra in un intero con segno a 32 bit.

Esempi

Input: nums = [3, 4, -7, 1, 3, 3, 1, -4]k = 7
Output: 4
Spiegazione: Quattro sequenze hanno somma 7: [3, 4], [1, 3, 3], [3, 3, 1] e [3, 4, -7, 1, 3, 3]. Nell’ultima, -7 annulla il 3 e il 4, e la somma risale a 7 più avanti, quindi una sequenza può corrispondere anche dopo che la sua somma ha superato k.

Input: nums = [1, -1, 0]k = 0
Output: 3
Spiegazione: Tre sottoarray hanno una somma pari a 0: [1, -1], [0] e l'intero array [1, -1, 0]. La sequenza [-1, 0] ha una somma pari a -1, quindi non conta.

Input: nums = [2, 2, 2]k = 4
Output: 2
Spiegazione: La sequenza [2, 2] agli indici 0 e 1 e la sequenza [2, 2] agli indici 1 e 2 contengono gli stessi valori ma si trovano in posizioni diverse, quindi contano entrambe. La somma dell'intero array è 6.

+17 test nascosti all’invio

Per approfondire

Come modificheresti la soluzione per restituire la lunghezza del sottarray più lungo la cui somma è k, sempre in tempo O(n)?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Un array di n numeri ha n(n+1)/2 sottoarray, circa 2 × 10^8 quando n = 2 × 10^4, quindi sommarli uno per uno è troppo lento. Anche i valori negativi escludono una finestra scorrevole: la somma di una finestra può diminuire e poi aumentare di nuovo, quindi nessuna regola ti dice quando restringerla. L’idea che risolve il problema consiste nello scrivere ogni somma di sottoarray come differenza di due somme prefisse. Contare i sottoarray che terminano con l’elemento corrente e la cui somma è k significa quindi contare le somme prefisse precedenti uguali a quella corrente meno k; una mappa hash permette di farlo in un’unica passata.

Ogni inizio con un totale progressivo

Corretto, ma non termina sui test più grandi

Intuizione

Ogni sottoarray ha un indice iniziale start e un indice finale end. Se visiti ogni coppia e ne controlli la somma, consideri ogni sottoarray esattamente una volta, quindi il conteggio è corretto.

Non ti serve un terzo ciclo per sommare ogni sottoarray. Fissa start, poi sposta end di un passo alla volta verso destra e aggiungi nums[end] a un total cumulativo. Il totale contiene sempre la somma degli elementi da start a end, quindi ogni sottoarray richiede un'addizione e un confronto.

Non fermarti quando il totale raggiunge o supera k. Un valore negativo successivo può riportarlo indietro: nel primo esempio, il totale dall'indice 0 passa per 3, 7, 0, 1, 4, 7, quindi quel punto di partenza ha una seconda corrispondenza all'indice 5.

Il costo è pari al numero di coppie. Con n = 2 × 10^4 ce ne sono circa 2 × 10^8, un numero gestibile in C, ma decisamente troppo lento per Python, Ruby o R.

Algoritmo

Imposta count a 0.
Per ogni start da 0 a n-1, imposta total a 0.
Per ogni end da start a n-1, aggiungi nums[end] a total.
Se total è uguale a k, aggiungi 1 a count e continua comunque.
Restituisci count.

def subarraySum(nums, k):
    n = len(nums)
    count = 0
    for start in range(n):
        total = 0
        # Grow the subarray that begins at start, one element at a time
        for end in range(start, n):
            total += nums[end]
            if total == k:
                count += 1
    return count

Somme prefisse con una mappa dei conteggi

Intuizione

Sia prefix[j] la somma dei primi j elementi, con prefix[0] = 0 per il prefisso vuoto. Il sottoarray dall’indice i all’indice j-1 ha somma prefix[j] - prefix[i]. Quindi un sottoarray che termina nell’elemento corrente ha somma k esattamente quando una somma prefissa precedente è uguale alla somma prefissa corrente meno k. Ogni somma prefissa precedente di questo tipo indica l’inizio di un sottoarray corrispondente.

Scorri l’array una sola volta. Tieni traccia della somma prefissa progressiva e di una mappa hash seen che associa ogni somma prefissa al numero di volte che è apparsa. Per ogni elemento, aggiungi prima seen[prefix - k] al conteggio, poi registra la somma prefissa corrente. Cercare prima di registrare evita che un sottoarray sia vuoto: con k = 0, registrare per primo farebbe corrispondere la somma prefissa corrente a sé stessa.

Considera il primo esempio con k = 7. Le somme prefisse sono 0, 3, 7, 0, 1, 4, 7, 8, 4. Quando la somma prefissa raggiunge 7 dopo l’indice 1, la mappa contiene un solo 0, che corrisponde a [3, 4]. Quando raggiunge di nuovo 7 dopo l’indice 5, la mappa contiene due 0, il prefisso vuoto e il prefisso dopo il -7, che corrispondono rispettivamente a [3, 4, -7, 1, 3, 3] e [1, 3, 3]. A 8 dopo l’indice 6, la mappa contiene un solo 1, che corrisponde a [3, 3, 1]. Il totale è quindi 4.

Inizializzare la mappa con 0 presente una volta permette di contare i sottoarray che iniziano all’indice 0. È importante usare una mappa di conteggi invece di un insieme, perché la stessa somma prefissa può ripetersi e ogni occorrenza dà inizio a un sottoarray diverso. Per ogni elemento si eseguono una ricerca e un aggiornamento, quindi il tempo di esecuzione è O(n) e la mappa contiene al massimo n+1 chiavi.

Algoritmo

Crea una mappa seen con seen[0] = 1 e imposta prefix e count a 0.
Per ogni elemento, aggiungilo a prefix.
Aggiungi seen[prefix - k] a count, leggendo una chiave mancante come 0.
Aggiungi 1 a seen[prefix].
Restituisci count.

def subarraySum(nums, k):
    # seen[p] = how many prefixes so far add up to p; the empty prefix adds up to 0
    seen = {0: 1}
    prefix = 0
    count = 0
    for num in nums:
        prefix += num
        # Each earlier prefix equal to prefix - k starts a subarray that ends here and sums to k
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

Trappole e casi limite

La maggior parte delle risposte errate deriva dal trattare l’input come se ogni valore fosse positivo oppure dall’ordine delle due operazioni sulla mappa.

Una finestra scorrevole che si restringe quando la somma supera k non funziona con valori negativi. Nel primo esempio restituisce 2 invece di 4: la finestra mantiene il bordo sinistro all’indice 0 finché la somma supera 7 all’indice 6, quindi non prova mai [1, 3, 3] o [3, 3, 1].
Omettere seen[0] = 1 fa perdere tutti i sottarray che iniziano all’indice 0. Per nums = [5] e k = 5 restituisce 0 invece di 1.
Registrare il prefisso corrente prima della ricerca conta i sottarray vuoti quando k è 0. Per [1, -1, 0] restituisce 6 invece di 3.
Usare un insieme di somme prefisse al posto di una mappa di conteggi sottostima le ripetizioni. Per [0, 0, 0] e k = 0 la risposta è 6, perché ogni occorrenza precedente della stessa somma prefissa dà inizio a un sottarray diverso.
Nella soluzione con forza bruta, interrompere il ciclo interno quando il totale supera k è sbagliato per lo stesso motivo per cui è sbagliata la finestra scorrevole.

Domande frequenti4

Qual è la complessità temporale di Subarray Sum Equals K?

La soluzione con somme prefisse e mappa hash richiede un tempo O(n) e uno spazio aggiuntivo O(n): una sola scansione, con una ricerca e un aggiornamento per ogni elemento. Controllare ogni sottarray con un totale progressivo richiede un tempo O(n²), mentre sommare da zero gli elementi di ogni sottarray richiede un tempo O(n³).

Perché una finestra scorrevole non funziona per il problema della somma del sottoarray uguale a K?

Una finestra scorrevole si basa sul fatto che la somma aumenta quando la finestra si allarga e diminuisce quando si restringe, cosa che vale solo quando tutti i valori sono positivi. Con valori negativi, una finestra la cui somma è già troppo grande può comunque diventare una corrispondenza se si allarga ulteriormente, quindi nessuna regola ti dice quando spostare il bordo sinistro. Se tutti i valori fossero positivi, una finestra scorrevole risolverebbe il problema in tempo O(n) e spazio O(1).

Perché la mappa hash inizia con 0 mappato a 1?

Quella voce rappresenta il prefisso vuoto prima del primo elemento, la cui somma è 0. Un sottarray che inizia all’indice 0 ha come somma la somma del prefisso corrente meno quel prefisso vuoto, quindi senza quella voce tali sottarray non vengono mai conteggiati. Per nums = [5] e k = 5, la ricerca di 5 - 5 = 0 trova quella voce e restituisce 1.

È possibile risolvere Subarray Sum Equals K con O(1) spazio aggiuntivo?

Non con il metodo a un solo passaggio. Per contare le corrispondenze che terminano in un elemento, devi sapere quali somme prefisse lo precedono, e ce ne possono essere fino a n+1 diverse. Senza la mappa, torni al totale progressivo O(n²). Quando tutti i valori sono positivi, una finestra scorrevole conta i sottoarray in O(n) tempo e O(1) spazio.

Python

def subarraySum(nums, k):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

nums = [3, 4, -7, 1, 3, 3, 1, -4]
k = 7

Atteso