4Sum

Q: Qual è la complessità temporale di 4Sum?

O(n³). I due cicli selezionano circa n²/2 coppie (i, j) e per ciascuna viene eseguita una scansione con due puntatori di al massimo n passaggi; l'ordinamento O(n log n) è trascurabile rispetto a questo.

Q: Come si generalizza 4Sum a kSum?

Scrivi kSum(nums, target, k) su una lista ordinata. Per k = 2 esegue una scansione a due puntatori. Per un k più grande, scorre il primo valore, salta i duplicati e richiama se stessa con k-1 e target - nums[i] sui valori a destra. Ogni livello aggiunge un fattore n, quindi kSum ha costo O(n^(k-1)).

Q: È possibile risolvere 4Sum in O(n²)?

Puoi raggruppare le n²/2 somme delle coppie in una mappa hash e abbinare ogni coppia con le coppie la cui somma è target meno la sua. È veloce quando poche coppie condividono la stessa somma, ma una somma può contenere O(n²) coppie, quindi nel caso peggiore non è migliore di O(n³).

MedioDue puntatori Ordinamento

+10

Ti viene fornito un elenco di numeri interi nums e un numero intero target. Restituisci ogni quadrupla [a, b, c, d] i cui quattro valori si trovano in quattro posizioni diverse di nums e la cui somma è uguale a target. Scrivi ogni quadrupla con i valori in ordine non decrescente. Se gli stessi quattro valori possono essere scelti da posizioni diverse, la quadrupla compare comunque una sola volta. Ordina la risposta in base al primo valore, poi al secondo e infine al terzo. Se nessuna quadrupla è valida, restituisci un elenco vuoto.

Funzione

fourSum(nums: integer-array, target: integer) → integer-2d-array

numsinteger-array: i numeri tra cui scegliere, almeno uno
targetinteger: la somma che ogni quadrupla deve raggiungere
Restituisceinteger-2d-array: le quadrupletti distinti con somma target, ciascuno ordinato, anche la lista ordinata; una lista vuota se non ce ne sono

Vincoli

1 ≤ nums.length ≤ 200
-10⁸ ≤ nums[i] ≤ 10⁸
-10⁹ ≤ target ≤ 10⁹
La somma di quattro valori qualsiasi è compresa tra -4 × 10⁸ e 4 × 10⁸, quindi rientra in un intero a 32 bit.
Le quadruplette che contengono gli stessi quattro valori contano come una sola.

Esempi

Input: nums = [3, -1, 0, 2, -2, 1, -3]target = 1
Output: [[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]
Spiegazione: Ciascuna delle quattro quadruple ha una somma pari a 1, ad esempio -3 + (-1) + 2 + 3. Le due che iniziano con -3 vengono per prime, ordinate in base al secondo valore: -1 prima di 0.

Input: nums = [4, 4, 4, 4, 4, 4]target = 16
Output: [[4, 4, 4, 4]]
Spiegazione: Tutte le 15 combinazioni di quattro posizioni su sei danno quattro 4 che sommano 16, quindi [4, 4, 4, 4] compare una volta.

Input: nums = [1, 5, 2, 9]target = 3
Output: []
Spiegazione: L'unica scelta è usare tutti e quattro i numeri, e 1 + 5 + 2 + 9 = 17, non 3, quindi la risposta è una lista vuota.

Per approfondire

Conta gli insiemi di quattro posizioni i cui valori sommano a target, anziché le quadruple distinte. Il secondo esempio ne ha 15. Riesci a farlo in O(n²)?

Suggerimenti

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

0 di 3 aperti

Soluzione

Controllare ogni insieme di quattro posizioni costa O(n⁴) e i valori ripetuti formano più volte la stessa quadrupla. Applica la riduzione del 3Sum un livello più in profondità: ordina, fissa i primi due valori con due cicli, trova l’ultima coppia con due puntatori e salta i valori ripetuti a ogni livello.

Prova ogni gruppo di quattro

Corretto, ma non termina sui test più grandi

Intuizione

Ordina prima, così le posizioni i < j < k < l contengono valori in ordine non decrescente e ogni quadrupla viene scritta nel modo giusto. Quattro cicli annidati raggiungono ogni possibile scelta di quattro posizioni. Per evitare ripetizioni, un ciclo passa oltre quando la posizione successiva contiene il valore che ha provato un passo prima. Con sei 4, ogni ciclo prova solo la sua prima posizione, quindi [4, 4, 4, 4] viene restituita una sola volta invece di 15 volte.

Per 200 numeri ci sono 64,684,950 insiemi di quattro elementi, e il conteggio cresce di circa 16 volte quando n raddoppia.

Algoritmo

Ordina nums.
Annida quattro cicli su i < j < k < l, ciascuno iniziando una posizione dopo il ciclo che lo contiene.
In ogni ciclo, salta una posizione che non è la prima del ciclo e contiene lo stesso valore della posizione precedente.
Registra [nums[i], nums[j], nums[k], nums[l]] quando i quattro valori sommati danno target. I cicli li producono in ordine crescente.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 2):
            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 - 1):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                for l in range(k + 1, n):
                    if l > k + 1 and nums[l] == nums[l - 1]:
                        continue  # same fourth value as the round before
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        quads.append([nums[i], nums[j], nums[k], nums[l]])
    return quads

Ordinamento, due cicli, due puntatori

Intuizione

Fissa nums[i] e nums[j], e ciò che resta è un problema di coppie: trova due valori a destra di j la cui somma sia target - nums[i] - nums[j]. Su una lista ordinata basta una sola scansione. Inizia con lo a j+1 e hi all’ultimo indice. Una somma inferiore a target sposta lo a destra; una somma superiore sposta hi a sinistra.

Ogni spostamento elimina un valore che non può far parte di alcuna soluzione. Se la somma è troppo piccola, nemmeno il valore più grande rimasto, nums[hi], è sufficiente per nums[lo], quindi si può eliminare nums[lo]. Una somma troppo grande elimina nums[hi] per il motivo speculare. Una coppia (i, j) richiede al massimo n spostamenti, quindi le n²/2 coppie hanno un costo O(n³).

Nel primo esempio, con i su -3 e j su -1, lo si sposta da 0, supera 1 e arriva a 2, dove -3 + (-1) + 2 + 3 = 1.

Algoritmo

Ordina nums.
Per ogni i, saltalo quando i > 0 e nums[i] è uguale a nums[i-1].
Per ogni j dopo i, saltalo quando j > i+1 e nums[j] è uguale a nums[j-1].
Imposta lo = j+1 e hi = n-1. Mentre lo < hi, confronta la somma dei quattro valori con target: se è minore, sposta lo a destra; se è maggiore, sposta hi a sinistra.
In caso di corrispondenza, registra la quadrupla, sposta entrambi i puntatori, poi avanza lo mentre contiene il valore appena utilizzato.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # this second value was already handled
            lo, hi = j + 1, n - 1
            while lo < hi:
                total = nums[i] + nums[j] + nums[lo] + nums[hi]
                if total < target:
                    lo += 1
                elif total > target:
                    hi -= 1
                else:
                    quads.append([nums[i], nums[j], nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
    return quads

Trappole e casi limite

Saltare j ogni volta che nums[j] è uguale a nums[j-1]. Quando j = i+1, il confronto avviene con il valore usato da i, quindi [2, 2, 2, 2, 2] con obiettivo 8 perde [2, 2, 2, 2].
Copiare l’uscita anticipata di 3Sum nums[i] > target. Con [-5, -4, -3, -2, -1] e obiettivo -10, il ciclo si interrompe a -5 e non trova [-4, -3, -2, -1].
Liste con meno di quattro elementi. Con uno o due numeri n-3 è negativo: 0..<(n - 3) causa un errore in Swift, mentre n - 3 su un usize di Rust va in underflow. Restituisci prima una lista vuota.
Raccogliere le quadruple in un set hash e restituirle non ordinate.

Domande frequenti3

Qual è la complessità temporale di 4Sum?

O(n³). I due cicli selezionano circa n²/2 coppie (i, j) e per ciascuna viene eseguita una scansione con due puntatori di al massimo n passaggi; l'ordinamento O(n log n) è trascurabile rispetto a questo.

Come si generalizza 4Sum a kSum?

Scrivi kSum(nums, target, k) su una lista ordinata. Per k = 2 esegue una scansione a due puntatori. Per un k più grande, scorre il primo valore, salta i duplicati e richiama se stessa con k-1 e target - nums[i] sui valori a destra. Ogni livello aggiunge un fattore n, quindi kSum ha costo O(n^(k-1)).

È possibile risolvere 4Sum in O(n²)?

Puoi raggruppare le n²/2 somme delle coppie in una mappa hash e abbinare ogni coppia con le coppie la cui somma è target meno la sua. È veloce quando poche coppie condividono la stessa somma, ma una somma può contenere O(n²) coppie, quindi nel caso peggiore non è migliore di O(n³).

def fourSum(nums, target):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso

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