Two Sum
Ti viene fornito un array di numeri interi nums e un numero intero target. Esattamente due elementi di nums, in due posizioni diverse, sommati danno target. Restituisci gli indici di quei due elementi, con l'indice più piccolo per primo.
Funzione
- numsinteger-array
- l’array di interi in cui cercare
- targetinteger
- la somma deve raggiungere i due valori
- Restituisceinteger-array
- i due indici, prima quello più piccolo
Vincoli
2 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109-109 ≤ target ≤ 109- Esattamente una coppia di posizioni distinte ha come somma
target.
Esempi
- Input
- nums = [3, 8, 12, 5]target = 17
- Output
- [2, 3]
- Spiegazione
- 12 si trova all'indice 2 e 5 all'indice 3, e 12 + 5 = 17. Nessun'altra coppia raggiunge 17.
- Input
- nums = [6, 1, 4, 10]target = 7
- Output
- [0, 1]
- Spiegazione
- 6 all’indice 0 e 1 all’indice 1 fanno 7: la coppia può essere i primi due elementi.
- Input
- nums = [2, -6, 9, 4, 13]target = 3
- Output
- [1, 2]
- Spiegazione
- -6 all'indice 1 e 9 all'indice 2 fanno 3. I numeri negativi si abbinano proprio come quelli positivi.
Per approfondire
Se nums fosse già arrivato ordinato, riusciresti a trovare la coppia in tempo O(n) usando solo O(1) di memoria aggiuntiva?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Provare ogni coppia con due cicli annidati è corretto, ma con 10.000 numeri significa circa 50 milioni di controlli. Riesci a trovare il numero complementare di ciascun numero senza scorrere di nuovo l’elenco?
Quando ti trovi su un valore
x, sai già quale valore completerebbe la coppia: il target menox. L’unica domanda è se hai già incontrato quel valore e a quale indice.Scorri la lista una volta e mantieni una mappa hash che associ a ogni valore già incontrato il suo indice. A ogni posizione, cerca prima il valore complementare mancante; se è nella mappa, hai entrambi gli indici. Altrimenti, memorizza il valore corrente e prosegui. Cercare prima di memorizzare è ciò che impedisce a un numero di essere abbinato a sé stesso.
Soluzione
Controllare ogni coppia funziona, ma il lavoro cresce con il quadrato della lunghezza. Capovolgi la domanda: trovandoti su un numero x, sai già che il suo partner deve essere target - x. Una mappa hash ti dice in tempo costante se hai già incontrato quel valore, quindi basta un solo passaggio.
Controlla ogni coppia
Corretto, ma non termina sui test più grandi
Intuizione
Fissa un primo indice i e prova ogni indice j alla sua destra finché nums[i] + nums[j] non è uguale a target. Iniziare j da i + 1 impedisce a una posizione di essere abbinata a se stessa, prova ogni coppia una sola volta e mette prima l’indice più piccolo. La coppia che cerchi è tra quelle che provi, quindi la trovi.
n numeri formano circa n²/2 coppie: n = 10^4 significa quasi 5 × 10^7 addizioni.
Algoritmo
- Esegui il ciclo di
isu ogni indice dinums. - Per ogni
i, esegui il ciclo dijdai + 1fino all’ultimo indice. - Se
nums[i] + nums[j]è uguale atarget, restituisci[i, j]. - Se entrambi i cicli terminano, restituisci un array vuoto. Il problema garantisce che questo non accadrà mai.
def twoSum(nums, target):
n = len(nums)
for i in range(n):
# Only look at partners to the right, so each pair is checked once.
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []Un passaggio con una mappa hash
Intuizione
Per un nums[i] fissato, il ciclo interno dell’approccio esaustivo cerca un valore che conosci già in anticipo: target - nums[i]. Quella scansione è una ricerca mascherata, e una mappa hash da valore a indice esegue ricerche in tempo costante in media.
Cerca prima, memorizza dopo. In questo modo un numero può essere abbinato solo a qualcosa che lo precede, mai a sé stesso, e poiché il suo abbinamento è sempre precedente, il suo indice viene prima. Ogni numero viene visitato una volta con operazioni sulla mappa in tempo costante, quindi la ricerca è O(n); il prezzo è una mappa con fino a n voci.
Algoritmo
- Crea una mappa vuota da valore a indice.
- Per ogni indice
i, calcolaneed, il valore che completa la coppia:targetmenonums[i]. - Se
needè nella mappa, restituisci il suo indice memorizzato seguito dai. - Altrimenti memorizza
nums[i]con l’indiceie continua.
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
need = target - num
if need in seen:
return [seen[need], i]
seen[num] = i
return []
Trappole e casi limite
- Memorizzare un numero prima di cercare il suo complemento. Con
[4, 2, 6]etarget = 8, il 4 trova sé stesso e restituisci[0, 0]. - Restituire gli indici nell'ordine sbagliato. Se cerchi prima di memorizzare, l'indice della mappa è quello più piccolo e va per primo.
- Ordinare l'array per usare due puntatori, quindi restituire le posizioni nella copia ordinata. Mantieni l'indice originale accanto a ciascun valore.
- Supporre che i valori siano positivi o distinti.
[0, 7, -3, 0]contarget = 0abbina i due zeri:[0, 3]. - In Lua e R, restituire gli indici basati su 1. Sottrai 1 da ciascuno.
Domande frequenti3
Qual è la complessità temporale di Two Sum?
La soluzione con tabella hash richiede O(n) tempo, perché visita ogni numero una volta e ogni ricerca o inserimento richiede in media un tempo costante. Usa O(n) spazio aggiuntivo per la mappa. Controllare ogni coppia richiede O(n²) tempo e O(1) spazio.
È possibile risolvere Two Sum senza spazio aggiuntivo?
Non in tempo lineare su un array non ordinato. Con O(1) di spazio aggiuntivo torni a controllare ogni coppia, che richiede O(n²). La mappa hash scambia O(n) di memoria con un tempo lineare.
In che modo Two Sum gestisce i numeri duplicati?
I duplicati funzionano quando cerchi il valore complementare prima di memorizzare il numero corrente. In [7, 3, 7] con target = 14, il primo 7 viene memorizzato all'indice 0 e il secondo 7 lo trova, restituendo [0, 2]. Un 7 isolato non si abbina mai a se stesso: non è ancora nella mappa quando lo cerchi.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def twoSum(nums, target):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
nums = [3, 8, 12, 5] target = 17
Output atteso
[2, 3]