3Sum

+10

Ti viene fornito un elenco di numeri interi nums. Trova tutte le triplette [a, b, c] di valori presi da tre posizioni diverse di nums tali che a + b + c = 0. Scrivi ogni tripletta in ordine non decrescente (a ≤ b ≤ c) ed elenca ogni tripletta distinta una sola volta, anche quando diverse combinazioni di posizioni la producono. Restituisci le triplette ordinate in base al primo valore e poi al secondo.

Funzione

threeSum(nums: integer-array) → integer-2d-array

numsinteger-array: l'elenco di numeri interi, con almeno tre elementi
Restituisceinteger-2d-array: ogni terna distinta la cui somma è 0, ciascuna in ordine non decrescente, l’elenco ordinato

Vincoli

3 ≤ nums.length ≤ 3000
-10⁵ ≤ nums[i] ≤ 10⁵
Almeno una terna ha somma pari a 0.
Due triplette sono uguali quando contengono gli stessi tre valori.

Esempi

Input: nums = [-2, 0, 1, 1, -1, 2]
Output: [[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
Spiegazione: -2 + 0 + 2, -2 + 1 + 1 e -1 + 0 + 1 danno tutti 0. [-2, 1, 1] può usare il valore 1 due volte perché 1 si trova in due posizioni, mentre [-1, 0, 1] può essere composto usando uno dei due 1, ma compare una sola volta.

Input: nums = [0, 0, 0, 0]
Output: [[0, 0, 0]]
Spiegazione: Tre qualsiasi dei quattro zeri sommano 0. Ci sono quattro possibili scelte delle posizioni, ma danno tutte la stessa terna, quindi la risposta conta [0, 0, 0] una sola volta.

+15 test nascosti all’invio

Per approfondire

Lo stesso schema risolve 4Sum: fissa due valori e usa due puntatori sul resto. Riesci a scriverlo in O(n³) e a gestire correttamente i duplicati a ogni livello?

Suggerimenti

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

0 di 3 aperti

Soluzione

Due cose rendono 3Sum più difficile di quanto sembri. Controllare ogni terna costa O(n³), e la risposta deve contenere ogni terna una sola volta anche quando i valori si ripetono. L’ordinamento risolve entrambi i problemi: i valori uguali finiscono uno accanto all’altro, quindi puoi saltare i duplicati confrontando gli elementi vicini; inoltre, una volta fissato il valore più piccolo, gli altri due formano un problema di somma di coppia su una lista ordinata che due puntatori risolvono con un’unica scansione.

Prova ogni terzina

Corretto, ma non termina sui test più grandi

Intuizione

Ordina prima la lista. Poi, per tre posizioni qualsiasi i < j < k, i valori sono già in ordine, nums[i] ≤ nums[j] ≤ nums[k], quindi una terna è scritta correttamente non appena la trovi. Tre cicli annidati visitano tutte le possibili scelte di posizioni, quindi non può sfuggire nessuna terna.

Ora occupiamoci dei valori ripetuti. Il primo esempio, una volta ordinato, è [-2, -1, 0, 1, 1, 2], e [-1, 0, 1] può prendere il suo 1 dall’indice 3 o dall’indice 4. Ogni ciclo salta quindi una posizione il cui valore è uguale a quello già provato dallo stesso ciclo. Ogni ciclo prova così una sola volta ogni valore distinto, e ogni terna distinta viene restituita una sola volta, già in ordine crescente. Il controllo dei duplicati confronta solo con la posizione precedente all’interno dello stesso ciclo, quindi [-2, 1, 1] usa comunque entrambi gli 1.

Il problema è il costo. Ci sono circa n³/6 terne: per 3000 numeri, sono 4,5 × 10^9 somme, un numero ben oltre qualsiasi limite di tempo.

Algoritmo

Ordina nums.
Fai scorrere i sulle posizioni e salta i quando nums[i] è uguale a nums[i-1].
Al suo interno, fai scorrere j a partire da i+1 e salta j quando j > i+1 e nums[j] è uguale a nums[j-1].
Al suo interno, fai scorrere k a partire da j+1 applicando la stessa regola per saltare, e registra [nums[i], nums[j], nums[k]] quando i tre numeri sommano a 0.
Restituisci le triplette nell’ordine in cui le hai trovate. Sono già ordinate.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 1):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # same second value as the round before
            for k in range(j + 1, n):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                if nums[i] + nums[j] + nums[k] == 0:
                    triplets.append([nums[i], nums[j], nums[k]])
    return triplets

Fissa un valore, trova la coppia con un insieme hash

Intuizione

Una volta fissato il primo valore nums[i], ti servono due valori successivi la cui somma sia -nums[i]. È Two Sum. Sposta j a destra di i e tieni un insieme dei valori che hai già incontrato. A ogni j, il valore mancante è need = -nums[i] - nums[j]. Se need è nell’insieme, [nums[i], need, nums[j]] ha somma 0. La ricerca in un insieme ha un costo medio O(1), quindi per un singolo i il costo è O(n) e la ricerca completa costa O(n²).

L’ordinamento si occupa comunque della gestione dei valori. Salta un i il cui valore è uguale a quello precedente. Dopo aver trovato una corrispondenza, sposta j oltre ogni copia di nums[j]: fissati il primo e il terzo valore, anche quello centrale è fissato, quindi un’altra copia potrebbe solo ripetere la stessa terna. Poiché need proviene da una posizione precedente nell’elenco ordinato, need ≤ nums[j] e la terna è in ordine. Puoi anche fermarti non appena nums[i] > 0: i due valori successivi sono almeno altrettanto grandi, quindi la somma non può arrivare a 0.

Un dettaglio: mentre j si sposta a destra, nums[j] aumenta e need diminuisce, quindi le terne per uno stesso i vengono trovate con il valore centrale in ordine decrescente. In [-2, -1, 0, 1, 1, 2] con i = 0, trovi [-2, 1, 1] al secondo 1 e poi [-2, 0, 2] al 2. Inverti ogni gruppo prima di aggiungerlo alla risposta. Le versioni C e R contrassegnano i valori già visti in un array indicizzato per valore invece di usare un insieme hash, possibile perché ogni valore è compreso tra ±10^5.

Algoritmo

Ordina nums.
Per ogni i, fermati quando nums[i] > 0 e salta i quando nums[i] è uguale a nums[i-1].
Inizia con un insieme vuoto. Per ogni j a partire da i+1, calcola need = -nums[i] - nums[j]. Se need è nell'insieme, registra [nums[i], need, nums[j]] e sposta j oltre le copie di nums[j].
Aggiungi nums[j] all'insieme e passa al j successivo.
Inverti le triplette trovate per questo i e aggiungile alla risposta.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        group = []
        seen = set()  # values between position i and position j
        j = i + 1
        while j < n:
            need = -nums[i] - nums[j]
            if need in seen:
                group.append([nums[i], need, nums[j]])
                while j + 1 < n and nums[j + 1] == nums[j]:
                    j += 1
            seen.add(nums[j])
            j += 1
        # need shrinks as nums[j] grows, so this group came out backwards
        group.reverse()
        triplets.extend(group)
    return triplets

Ordina e usa due puntatori

Intuizione

L’ordine ordinato può sostituire l’insieme. Fissa nums[i], posiziona lo su i+1 e hi sull’ultimo indice, quindi osserva nums[i] + nums[lo] + nums[hi]. Se il risultato è inferiore a 0, serve un valore più grande, quindi lo si sposta a destra. Se è superiore a 0, serve un valore più piccolo, quindi hi si sposta a sinistra. Se è esattamente 0, registra la terna e sposta entrambi.

Non si perde nessuna terna. Quando la somma è inferiore a 0, nums[lo] è troppo piccolo anche abbinandolo al valore più grande rimasto, nums[hi], quindi non può essere abbinato a nessun valore ancora nell’intervallo e scartarlo non comporta alcuna perdita. Il caso superiore a 0 è speculare: nums[hi] è troppo grande anche abbinandolo al valore più piccolo rimasto. Ogni passaggio scarta definitivamente un valore, quindi un i richiede al massimo n passaggi e l’intera ricerca O(n²), senza usare memoria oltre a quella necessaria per l’ordinamento e l’output.

Considera [-2, -1, 0, 1, 1, 2] ordinato. Con i = 0 (valore -2), lo parte da -1 e hi da 2: la somma è -1, quindi lo si sposta su 0. Ora -2 + 0 + 2 = 0, quindi registri [-2, 0, 2] ed entrambi i puntatori arrivano sui due 1, che producono [-2, 1, 1]. Con i = 1 (valore -1), 0 e 2 danno 1, quindi hi si sposta sul secondo 1, e -1 + 0 + 1 = 0 registra [-1, 0, 1]. Il valore 0 in corrispondenza di i = 2 non trova nulla, e in corrispondenza di i = 3 il valore è positivo, quindi la ricerca si interrompe.

Per i valori ripetuti servono due regole. Salta un i il cui valore è uguale a quello precedente. Dopo una corrispondenza, fai avanzare lo oltre le copie del valore utilizzato. hi non ha bisogno di una regola propria: quando lo si trova su un valore più grande, una copia del vecchio nums[hi] dà ora una somma superiore a 0 e si sposta autonomamente. Poiché i visita i valori distinti in ordine crescente e lo si sposta solo a destra, le terne risultano ordinate.

Algoritmo

Ordina nums.
Per ogni i, fermati quando nums[i] > 0 e salta i quando nums[i] è uguale a nums[i-1].
Imposta lo = i+1 e hi = n-1. Mentre lo < hi, somma nums[i], nums[lo] e nums[hi].
Se la somma è minore di 0, sposta lo a destra. Se è maggiore di 0, sposta hi a sinistra.
Se è 0, registra la terna, sposta entrambi i puntatori, poi sposta lo oltre le copie del valore utilizzato.
Restituisci le terne. Sono già ordinate.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            if total < 0:
                lo += 1
            elif total > 0:
                hi -= 1
            else:
                triplets.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
    return triplets

Trappole e casi limite

La maggior parte delle risposte errate è dovuta a valori ripetuti, quindi verifica il codice con input che li contengano.

Saltare i quando nums[i] è uguale a nums[i+1] mantiene l’ultima copia di ogni valore come primo elemento e le copie che la precedono vengono eliminate. In [-1, -1, 2], questo elimina [-1, -1, 2]. Confronta con la posizione precedente, nums[i-1].
Fermarsi quando nums[i] ≥ 0 invece che quando nums[i] > 0 non rileva [0, 0, 0].
Rimuovere i duplicati alla fine invece di saltarli. Con 3000 zeri, il ciclo a due puntatori registra milioni di copie di [0, 0, 0] prima di qualsiasi operazione di pulizia e, in diversi linguaggi, un insieme di liste confronta le liste per identità, quindi le copie rimangono comunque.
Usare due volte la stessa posizione. Una versione con hash set che riempie l’insieme con l’intera lista fin dall’inizio trasforma [-2, 1, 3] in [-2, 1, 1] usando due volte l’unico 1. Cerca i valori solo nelle posizioni che hai già superato.
Restituire le triplette senza rispettare l’ordine. Il confronto è esatto, quindi la versione con hash set deve invertire ogni gruppo, e una soluzione che raccoglie le triplette in un insieme deve ordinarle alla fine.

Domande frequenti4

Qual è la complessità temporale di 3Sum?

La soluzione con ordinamento e due puntatori richiede un tempo O(n²). L'ordinamento costa O(n log n) e ciascuna delle n scelte del primo valore richiede una scansione O(n). Richiede O(1) spazio aggiuntivo, a parte quello necessario per l'ordinamento e l'output. Controllare ogni tripla richiede invece O(n³).

In che modo 3Sum evita le triplette duplicate?

Ordina l’elenco, così i valori uguali si trovano uno accanto all’altro. Poi salta un primo valore uguale a quello che lo precede e, dopo ogni corrispondenza, sposta il puntatore sinistro oltre le copie del valore che ha usato. Ogni tripletta viene trovata una sola volta, partendo dalle prime copie dei suoi valori, quindi non serve un insieme di risultati.

Dovrei usare due puntatori o un insieme hash per 3Sum?

Entrambi hanno una complessità temporale O(n²). I due puntatori non richiedono memoria aggiuntiva e l’ordinamento ti restituisce le terzine già in ordine. Un insieme hash richiede O(n) di memoria e occorre fare attenzione a mantenere distinte le posizioni e a ordinare il risultato. L’idea dell’insieme hash è importante quando non puoi ordinare, come in Two Sum, dove restituisci gli indici originali.

È possibile risolvere il problema 3Sum più velocemente di O(n²)?

Non di molto. Gli algoritmi migliori conosciuti superano n² solo di pochi fattori logaritmici, e molti risultati di complessità nella geometria computazionale presuppongono che nessun algoritmo raggiunga una potenza di n inferiore a 2. Questi algoritmi più veloci sono risultati di ricerca, quindi O(n²) è la risposta che ci si aspetta nei colloqui.

Python

def threeSum(nums):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

nums = [-2, 0, 1, 1, -1, 2]

Atteso

[[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]

3Sum

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prova ogni terzina

Fissa un valore, trova la coppia con un insieme hash

Ordina e usa due puntatori

Trappole e casi limite

Domande frequenti4

Problemi simili