Minimum Size Subarray Sum
Ti vengono forniti un intero positivo target e un array nums di interi positivi. Trova il sottarray più corto (una sequenza di elementi adiacenti) la cui somma è almeno target e restituiscine la lunghezza. Se nessun sottarray raggiunge target, restituisci 0.
Funzione
- targetinteger
- la somma che un sottoarray deve raggiungere o superare
- numsinteger-array
- l'array di numeri interi positivi
- Restituisceinteger
- la lunghezza della sottosequenza contigua più corta con una somma almeno pari a target, oppure 0 se non ne esiste nessuna
Vincoli
1 ≤ target ≤ 1091 ≤ nums.length ≤ 2 × 1041 ≤ nums[i] ≤ 104
Esempi
- Input
- target = 15nums = [4, 2, 9, 3, 7, 1, 5]
- Output
- 3
- Spiegazione
- Nessuna coppia di numeri adiacenti raggiunge 15: la coppia più grande è 9 + 3 = 12. Tre numeri sì: 4 + 2 + 9 = 15 e 9 + 3 + 7 = 19, quindi la risposta è 3.
- Input
- target = 11nums = [1, 2, 3, 4]
- Output
- 0
- Spiegazione
- L’intero array dà come somma 10, meno di 11, quindi nessun sottoarray raggiunge il valore obiettivo e la risposta è 0.
- Input
- target = 8nums = [3, 8, 2]
- Output
- 1
- Spiegazione
- Il valore 8 raggiunge da solo il bersaglio e nessun sottoarray è più corto di un elemento.
+16 test nascosti all’invio
Per approfondire
Come lo risolveresti se nums potesse contenere anche zeri e numeri negativi, nel qual caso la finestra scorrevole non funziona più?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Tutti i valori sono positivi. Cosa succede alla somma di un sottoarray quando aggiungi un altro elemento a destra e quando ne rimuovi uno da sinistra?
Mantieni una finestra
nums[left..right]e la sua somma. Allargala a destra finché la somma raggiungetarget. A quel punto la finestra è una candidata e puoi provare ad accorciarla.Mentre la somma è almeno
target, registra la lunghezza della finestra e rimuovinums[left]. Entrambi i bordi si spostano solo verso destra, quindi ogni elemento entra ed esce dalla finestra una sola volta.
Soluzione
I valori sono tutti positivi, quindi estendere un sottoarray aumenta sempre la sua somma e tagliarlo la riduce sempre. Questo unico fatto è alla base di entrambe le soluzioni veloci. Le somme dei prefissi diventano una lista ordinata, quindi una ricerca binaria trova il punto in cui una somma raggiunge per la prima volta target. Ancora meglio, l'estremo migliore non si sposta mai a sinistra quando l'inizio si sposta a destra, quindi una singola finestra che cresce a destra e si restringe a sinistra trova la risposta in un unico passaggio.
Estendi da ogni inizio
Corretto, ma non termina sui test più grandi
Intuizione
Fissa un indice di partenza e aggiungi i valori uno alla volta verso destra. La prima volta che la somma progressiva raggiunge target, hai il sottarray più corto che inizia da quell'indice: tutti quelli più corti si sono fermati prima e la loro somma era ancora troppo piccola. Quindi registra la sua lunghezza, interrompi l'estensione e passa all'indice di partenza successivo. La risposta è la lunghezza minima tra tutti gli indici di partenza.
Con target = 15 e [4, 2, 9, 3, 7, 1, 5], partendo dall'indice 0 le somme sono 4, 6, 15 e ci si ferma alla lunghezza 3. Partendo dall'indice 1 le somme sono 2, 11, 14, 21 e ci si ferma alla lunghezza 4. Partendo dall'indice 2 le somme sono 9, 12, 19, e la lunghezza è di nuovo 3. Nessun indice di partenza permette di ottenere un risultato migliore di 3.
Il problema si presenta quando è difficile raggiungere il target. Se nessun sottarray lo raggiunge, da ogni indice di partenza si arriva fino alla fine dell'array: n(n+1)/2 addizioni, che equivalgono a 2 × 10^8 per n = 2 × 10^4. Inoltre, da ogni indice di partenza si ricalcolano somme già ottenute partendo dall'indice precedente.
Algoritmo
- Imposta
bestsu 0, perché non è ancora stato trovato nulla. - Per ogni indice iniziale, imposta a 0 una somma progressiva.
- Sposta un indice finale verso destra a partire dall'inizio, aggiungendo
nums[end]alla somma. - Quando la somma raggiunge
target, mantieniend-start+1se superabeste interrompi l'estensione da questo punto iniziale. - Restituisci
best.
def minSubArrayLen(target, nums):
n = len(nums)
best = 0 # 0 means no subarray found yet
for start in range(n):
total = 0
for end in range(start, n):
total += nums[end]
if total >= target:
# The shortest subarray from this start ends here
if best == 0 or end - start + 1 < best:
best = end - start + 1
break
return bestSomme prefisse e ricerca binaria
Intuizione
Sia prefix[k] la somma dei primi k valori, con prefix[0] = 0. La somma di nums[start..end-1] è quindi prefix[end] - prefix[start]. Per un inizio fissato, vuoi il valore minimo di end tale che prefix[end] ≥ prefix[start] + target.
Tutti i valori sono positivi, quindi prefix è strettamente crescente e per trovare la prima posizione in cui raggiunge un valore basta una ricerca binaria. Per [4, 2, 9, 3, 7, 1, 5], prefix è [0, 4, 6, 15, 18, 25, 26, 31]. Partendo dall'indice 2, ti serve 6 + 15 = 21; il primo valore di prefix maggiore o uguale a 21 è 25 all'indice 5, quindi la finestra è nums[2..4] = 9, 3, 7, di lunghezza 3.
Se persino prefix[n] è inferiore al valore richiesto per un inizio, nessun end funziona; e non ne esiste uno nemmeno per qualsiasi inizio successivo, poiché prefix[start] aumenta soltanto. Fermati lì. Sono n ricerche binarie, tempo O(n log n), più O(n) per l'array dei prefissi. Il valore massimo confrontato è 2 × 10^8 + 10^9, che rientra in un intero a 32 bit.
Algoritmo
- Crea
prefixdi lunghezzan+1, conprefix[k+1] = prefix[k] + nums[k]. - Per ogni posizione iniziale, calcola
need = prefix[start] + target. - Se
prefix[n] < need, fermati: nessuna posizione iniziale successiva può avere successo. - Esegui una ricerca binaria nelle posizioni da
start+1anper trovare il primoendtale cheprefix[end] ≥ need, e mantieniend-startse è la lunghezza più breve finora. - Restituisci la lunghezza più breve, oppure 0 se nessuna posizione iniziale ha avuto successo.
from bisect import bisect_left
def minSubArrayLen(target, nums):
n = len(nums)
# prefix[k] is the sum of the first k values; it only grows
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
best = 0
for start in range(n):
need = prefix[start] + target
if prefix[n] < need:
break # no window from here on can reach target
# The first end with prefix[end] >= need closes the shortest window
end = bisect_left(prefix, need, start + 1)
if best == 0 or end - start < best:
best = end - start
return bestFinestra scorrevole
Intuizione
Mantieni una finestra nums[left..right] e la sua somma. Sposta right di un passo alla volta e aggiungi il nuovo valore. Finché la somma è almeno target, la finestra è una candidata: registra la sua lunghezza, poi rimuovi nums[left] e sposta left in avanti per vedere se una finestra più corta funziona ancora.
Perché left può uscire definitivamente? Quando la finestra nums[left..right] raggiunge per la prima volta target, la finestra più piccola nums[left..right-1] non lo raggiungeva, perché il ciclo l'avrebbe ristretta al passaggio precedente. Quindi right è la fine più vicina per questo inizio, e qualsiasi fine successiva produce solo un sottarray più lungo. L'inizio ha già fornito la sua risposta migliore. Questo ragionamento richiede valori positivi: con un numero negativo, una finestra più lunga potrebbe avere in seguito una somma maggiore.
Con target = 15 e [4, 2, 9, 3, 7, 1, 5]: la somma sale a 4, 6, 15, quindi viene registrata una lunghezza di 3 e 4 esce (11). Aggiungendo 3 si ottiene 14, aggiungendo 7 si ottiene 21: registra la lunghezza 4, rimuovi 2 (19), registra la lunghezza 3, rimuovi 9 (10). Aggiungendo 1 e 5 si ottiene 16: registra la lunghezza 4, rimuovi 3 (13). La risposta è 3.
Il ciclo while si trova all'interno del ciclo for, eppure ogni indice entra nella finestra una volta e ne esce una volta, quindi il lavoro totale è O(n). Vengono memorizzati solo tre numeri, quindi lo spazio è O(1).
Algoritmo
- Imposta
left = 0,total = 0ebest = 0. - Per ogni
right, aggiunginums[right]atotal. - Finché
total ≥ target, conservaright-left+1se è maggiore dibest, sottrainums[left]e spostaleftdi un passo a destra. - Restituisci
best, che rimane 0 se la somma non ha mai raggiuntotarget.
def minSubArrayLen(target, nums):
best = 0 # 0 means no window found yet
total = 0 # sum of nums[left .. right]
left = 0
for right in range(len(nums)):
total += nums[right]
# Shrink while the window still reaches target
while total >= target:
if best == 0 or right - left + 1 < best:
best = right - left + 1
total -= nums[left]
left += 1
return best
Trappole e casi limite
La maggior parte dei bug si trova nella fase di riduzione della finestra e nel valore che restituisci quando nessuna finestra raggiunge target.
- Ridurre la finestra con
ifinvece diwhile. Pertarget = 12e[1, 1, 2, 3, 12], aggiungere 12 porta la somma a 19. Unifregistra la lunghezza 5, rimuove un valore e prosegue, quindi la finestra[12]di lunghezza 1 non viene mai misurata. Un ciclo continua a rimuovere valori finché la somma è ancora sufficiente. - Registrare la lunghezza dopo aver rimosso
nums[left]invece che prima. La finestra che misuri deve essere quella la cui somma ha raggiuntotarget. - Confrontare con
>invece che con≥. Un sott array la cui somma è uguale atargetconta:[3, 3, 3]contarget = 9ha risposta 3, non 0. - Restituire il valore sentinella. Se inizializzi
bestan+1o all'infinito, convertilo in 0 quando nulla ha raggiuntotarget. - Riutilizzare la finestra con array contenenti zeri o numeri negativi. Funziona solo se ogni valore è positivo; questo problema lo garantisce, ma le varianti no.
Domande frequenti4
Qual è la complessità temporale del problema «Somma di un sottoarray di dimensione minima»?
La soluzione con finestra scorrevole ha complessità temporale O(n) e spaziale O(1). Il ciclo interno potrebbe sembrare in grado di renderla quadratica, ma left si sposta solo in avanti, quindi nell'intera esecuzione avanza al massimo n volte. La versione con somme prefisse è O(n log n), mentre controllare ogni posizione di partenza è O(n²).
Perché la finestra mobile ha bisogno di numeri positivi?
Ridurre la finestra deve abbassarne la somma e ampliarla deve aumentarla, altrimenti eliminare l’elemento a sinistra potrebbe scartare l’inizio della risposta. Con i numeri negativi, quest’ordine viene meno. La soluzione abituale consiste nell’usare le somme prefisse con una deque monotona di possibili inizi, con un tempo di esecuzione che resta O(n).
Perché imparare la soluzione con somme prefisse O(n log n) se esiste O(n)?
Gli intervistatori spesso la chiedono dopo la risposta O(n). Mostra un secondo utilizzo dei valori positivi: le somme prefisse sono ordinate, quindi una ricerca binaria individua il punto in cui un totale progressivo supera per la prima volta una soglia. Questo strumento torna utile in altri problemi, per esempio quando si sceglie un indice a caso in proporzione al suo peso.
La somma del sottarray deve essere esattamente uguale al target?
No. Qualsiasi somma maggiore o uguale a target conta. Con target = 15, la finestra 9, 3, 7 ha una somma di 19 e ha comunque lunghezza 3. Se invece ti serve una somma esatta, la finestra funziona comunque con valori positivi: restringila finché la somma è superiore al target e registra una lunghezza solo quando è uguale.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def minSubArrayLen(target, nums):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
target = 15 nums = [4, 2, 9, 3, 7, 1, 5]
Atteso
3