Longest Subarray with Sum K

+10

Dati gli interi nums e un valore obiettivo k, restituisci la lunghezza della sottosequenza contigua più lunga la cui somma degli elementi è esattamente k. Una sottosequenza contigua è una sequenza di elementi consecutivi lunga almeno un elemento. Alcuni valori possono essere zero o negativi. Se nessuna sottosequenza contigua ha somma pari a k, restituisci 0.

Funzione

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

numsinteger-array: gli interi da cercare, inclusi i numeri negativi e gli zeri
kinteger: la somma esatta che deve avere il sottovettore
Restituisceinteger: la lunghezza della sottosequenza contigua più lunga la cui somma è k, oppure 0 se non ce n’è nessuna

Vincoli

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
-10⁹ ≤ k ≤ 10⁹
Ogni somma prefissa rimane compresa tra -2 × 10⁸ e 2 × 10⁸, quindi gli interi a 32 bit sono sufficienti.
Restituisci 0 quando nessun sottoarray ha somma pari a k.

Esempi

Input: nums = [2, -1, 3, 1, -4, 2, 3]k = 5
Output: 5
Spiegazione: Tre sequenze sommano a 5: [2, 3] alla fine, [2, -1, 3, 1] all'inizio e [3, 1, -4, 2, 3] agli indici da 2 a 6. L'ultima è la più lunga, con 5 elementi.

Input: nums = [4, 1, 1, 2, -1, 1]k = 3
Output: 4
Spiegazione: [1, 1, 2, -1] agli indici da 1 a 4 e [1, 2, -1, 1] agli indici da 2 a 5 hanno entrambi somma 3 con 4 elementi. Restituisci una lunghezza, quindi il pareggio non importa.

Per approfondire

Come troveresti il sottoarray più lungo la cui somma è al massimo k, consentendo comunque valori negativi?

Suggerimenti

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

0 di 3 aperti

Soluzione

Le somme cumulative trasformano la somma di qualsiasi sottoarray in una sola sottrazione: gli elementi dopo l'indice s fino all'indice i hanno una somma pari a prefix[i] - prefix[s]. Ricorda il primo indice in cui compare ogni totale e, con una sola passata, troverai la corrispondenza più lunga che termina in ogni posizione.

Cresci ogni sottoarray a partire da ciascun punto iniziale

Corretto, ma non termina sui test più grandi

Intuizione

Da ogni posizione iniziale, estenditi verso destra e aggiungi ogni elemento a un totale progressivo. Ogni volta che il totale è uguale a k, registra la lunghezza. Ogni sottovettore corrisponde a una coppia di posizione iniziale e posizione finale, quindi non ne viene tralasciato nessuno. Continua a estenderti anche dopo che il totale supera k: dall'indice 2 nel primo esempio i totali sono 3, 4, 0, 2, 5, e il -4 è il motivo per cui l'ultimo raggiunge 5.

Ci sono circa n²/2 coppie: 2 × 10^8 addizioni per n = 2 × 10^4.

Algoritmo

Imposta best su 0.
Per ogni start, imposta total su 0.
Sposta end da start fino all'ultimo indice e aggiungi nums[end] a total.
Quando total è uguale a k, imposta best sul valore maggiore tra best e end - start + 1.
Restituisci best.

def longestSubarrayWithSumK(nums, k):
    n = len(nums)
    best = 0
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            # A match may come after the total has passed k, so never stop early
            if total == k and end - start + 1 > best:
                best = end - start + 1
    return best

Somme prefisse con il primo indice di ogni somma

Intuizione

Una sequenza che termina all’indice i ha somma k esattamente quando un totale precedente è uguale a prefix - k. Se più totali precedenti soddisfano questa condizione, il primo dà inizio alla sequenza più lunga, quindi la mappa memorizza ogni totale solo la prima volta che compare. Una copia successiva potrebbe dare inizio solo a una sequenza più corta. Inizializza la mappa con il totale 0 all’indice -1, così una corrispondenza che inizia all’indice 0 ha lunghezza i + 1.

Nel primo esempio i totali sono 2, 1, 4, 5, 1, 3, 6. All’indice 6, 6 - 5 = 1 è comparso per la prima volta all’indice 1, il che dà una lunghezza pari a 5. Il totale 1 ricompare all’indice 4, e mantenere l’indice 1 è ciò che permette di trovare quella sequenza.

Una ricerca per elemento richiede un tempo O(n), e la mappa contiene al massimo n + 1 totali.

Algoritmo

Crea una mappa first che contenga il totale 0 all’indice -1 e imposta prefix e best a 0.
Per ogni indice i, aggiungi nums[i] a prefix.
Se prefix - k è nella mappa all’indice start, imposta best al valore maggiore tra best e i - start.
Se prefix non è ancora nella mappa, memorizzalo con l’indice i.
Restituisci best.

def longestSubarrayWithSumK(nums, k):
    # first[p] is the index where the prefix sum p first appears; the empty prefix sits at -1
    first = {0: -1}
    prefix = 0
    best = 0
    for i, num in enumerate(nums):
        prefix += num
        # The earliest prefix equal to prefix - k starts the longest match that ends at i
        start = first.get(prefix - k)
        if start is not None and i - start > best:
            best = i - start
        # Keep the first index only: a later one could only start a shorter subarray
        if prefix not in first:
            first[prefix] = i
    return best

Trappole e casi limite

Sovrascrivere ogni volta l’indice memorizzato quando un totale si ripete mantiene l’inizio più recente e trova una corrispondenza più breve. Il primo esempio restituisce 4 invece di 5, perché il totale 1 passa dall’indice 1 all’indice 4.
Anche una finestra che si restringe mentre la sua somma è maggiore di k restituisce 4 nel primo esempio. Termina contenendo [-1, 3, 1, -4, 2, 3], con somma 4, e non rimuove mai il -1.
Omettere il totale 0 all’indice -1 non rileva nessuna corrispondenza che inizi all’indice 0: [5, 0, 0, 0] con k = 5 restituisce 0 invece di 4.
L’indice memorizzato è la posizione prima del sottoarray, quindi la lunghezza è i - start. Aggiungere 1 conta un elemento di troppo.

Domande frequenti3

Qual è la complessità temporale del problema del sottarray più lungo con somma K?

Tempo O(n) e spazio aggiuntivo O(n) con somme progressive e una mappa dei primi indici: una ricerca e al massimo un inserimento per elemento. Estendere ogni sottoarray a partire da ciascun punto iniziale richiede tempo O(n²) e spazio O(1).

Perché una finestra scorrevole non funziona quando l’array contiene numeri negativi?

Una finestra scorrevole presuppone che aggiungere un elemento aumenti la somma e rimuoverne uno la diminuisca. Con valori negativi, una finestra la cui somma è troppo grande può comunque raggiungere k quando arriva un elemento negativo, mentre una la cui somma è troppo piccola potrebbe dover rimuovere un elemento negativo alla sua sinistra. La finestra non può stabilire quale mossa sia corretta.

È possibile risolvere il problema del sottoarray più lungo con somma K usando O(1) spazio aggiuntivo?

Solo quando nessun valore è negativo. In tal caso la somma non diminuisce mai man mano che la finestra cresce, e due puntatori trovano la finestra più lunga con somma k in tempo O(n) e spazio O(1). Con valori negativi ti serve la mappa dei totali oppure la scansione O(n²).

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

Test #1

Test #2

Test #3

Argomenti

nums = [2, -1, 3, 1, -4, 2, 3]
k = 5

Output atteso