Two Sum II: Sorted Input
Ricevi un array di numeri interi numbers ordinato in ordine non decrescente e un numero intero target. Esiste esattamente una coppia di posizioni diverse con due valori la cui somma è uguale a target. Restituisci quelle due posizioni come indici a base 0, prima l’indice più piccolo.
Funzione
- numbersinteger-array
- l’array ordinato di numeri interi
- targetinteger
- la somma che i due valori devono raggiungere
- Restituisceinteger-array
- i due indici a base zero [i, j] con i < j e numbers[i] + numbers[j] == target
Vincoli
2 ≤ numbers.length ≤ 104-5 × 108 ≤ numbers[i] ≤ 5 × 108-109 ≤ target ≤ 109numbersè ordinato in ordine non decrescente.- Esiste esattamente una coppia di indici
i < jtale chenumbers[i] + numbers[j] == target.
Esempi
- Input
- numbers = [-4, 1, 3, 8, 12]target = 9
- Output
- [1, 3]
- Spiegazione
- 1 si trova all'indice 1 e 8 all'indice 3, e 1 + 8 = 9. Nessun'altra coppia raggiunge 9: per esempio, -4 + 12 = 8.
- Input
- numbers = [2, 2, 5, 7]target = 4
- Output
- [0, 1]
- Spiegazione
- I due 2 agli indici 0 e 1 sono due posizioni diverse, quindi possono formare la coppia: 2 + 2 = 4.
- Input
- numbers = [-10, -3, 0, 6]target = -4
- Output
- [0, 3]
- Spiegazione
- -10 all'indice 0 e 6 all'indice 3 danno -10 + 6 = -4. La risposta può comprendere l'intero array.
+13 test nascosti all’invio
Per approfondire
Riesci a risolverlo in tempo O(n) con O(1) memoria aggiuntiva?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
L'array è ordinato. Guarda insieme il valore più piccolo e quello più grande. Che cosa ti dice la loro somma quando è inferiore a
target?Se la somma del primo valore e dell’ultimo è troppo piccola, il primo valore è troppo piccolo per ogni partner, perché l’ultimo valore è già il più grande. Puoi escluderlo.
Mantieni un puntatore a ciascuna estremità. Quando la somma è troppo piccola, sposta il puntatore sinistro verso destra; quando è troppo grande, sposta il puntatore destro verso sinistra. Fermati quando la somma è uguale a
target.
Soluzione
Una mappa hash risolve la versione non ordinata in un solo passaggio, ma richiede O(n) di memoria. Qui l’array è ordinato e quest’ordine ti indica in quale direzione muoverti. Posiziona un puntatore a ciascuna estremità. Se la somma è troppo piccola, solo un valore sinistro più grande può essere d’aiuto; se è troppo grande, solo un valore destro più piccolo può esserlo. A ogni passaggio si esclude definitivamente un valore, quindi un solo passaggio trova la coppia senza memoria aggiuntiva.
Controlla ogni coppia
Corretto, ma non termina sui test più grandi
Intuizione
Prova ogni coppia di posizioni i < j e verifica se numbers[i] + numbers[j] è uguale a target. Poiché i procede da sinistra e j inizia subito dopo, la prima coppia che trovi ha già l'indice più piccolo per primo.
È corretto, ma ignora l'ordine ordinato. Con n = 10^4 ci sono circa 5 × 10^7 coppie e, quando la risposta si trova vicino alla fine dell'array, le provi quasi tutte. È troppo lento per i test più grandi.
Algoritmo
- Fai scorrere
isu ogni indice. - Fai scorrere
jdai+1fino all'ultimo indice. - Se
numbers[i] + numbers[j]è uguale atarget, restituisci[i, j].
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n):
for j in range(i + 1, n):
if numbers[i] + numbers[j] == target:
return [i, j]
return []Ricerca binaria per ciascun partner
Intuizione
Una volta fissato il primo valore numbers[i], conosci esattamente il suo abbinamento: target - numbers[i]. La parte dell’array a destra di i è ordinata, quindi la ricerca binaria può dirti in O(log n) passaggi se quell’abbinamento è presente.
Per [-4, 1, 3, 8, 12] e target = 9: con i = 0 l’abbinamento sarebbe 13, che non è presente. Con i = 1 l’abbinamento è 8 e la ricerca lo trova all’indice 3. La risposta è [1, 3].
Cercare solo a destra di i mantiene per primo l’indice più piccolo e impedisce a un valore di essere abbinato a sé stesso. La coppia è unica, quindi il valore corrispondente compare al massimo una volta in quell’intervallo e qualsiasi corrispondenza è la risposta. In totale: n ricerche di O(log n) ciascuna.
Algoritmo
- Esegui un ciclo con
ida 0 an-2. - Calcola
need = target - numbers[i]. - Cerca
needcon la ricerca binaria negli indici dai+1an-1. - Se lo trovi in
mid, restituisci[i, mid].
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n - 1):
need = target - numbers[i]
lo, hi = i + 1, n - 1
while lo <= hi:
mid = (lo + hi) // 2
if numbers[mid] == need:
return [i, mid]
if numbers[mid] < need:
lo = mid + 1
else:
hi = mid - 1
return []Due puntatori da entrambe le estremità
Intuizione
Inizia con left = 0 e right = n-1 e osserva numbers[left] + numbers[right]. Se è uguale a target, hai finito. Se è troppo piccolo, numbers[left] non può far parte della risposta: anche abbinato al valore più grande ancora in gioco, non raggiunge il risultato. Quindi sposta left a destra. Se la somma è troppo grande, nemmeno numbers[right] può farne parte, perché anche il partner più piccolo rimasto porta a superare il risultato. Quindi sposta right a sinistra.
Ogni spostamento scarta un valore che non può mai far parte della coppia, mentre la coppia stessa non viene mai scartata. I puntatori si incontrano dopo al massimo n-1 spostamenti, quindi la scansione è O(n) e usa due variabili.
Con [-4, 1, 3, 8, 12] e target = 9: -4 + 12 = 8 è troppo piccolo, quindi left si sposta all'indice 1. Poi 1 + 12 = 13 è troppo grande, quindi right si sposta all'indice 3. Ora 1 + 8 = 9 e la risposta è [1, 3].
Algoritmo
- Imposta
lefta 0 erightan-1. - Mentre
left < right, calcolatotal = numbers[left] + numbers[right]. - Se
totalè uguale atarget, restituisci[left, right]. - Se
totalè minore, aggiungi 1 aleft; se è maggiore, sottrai 1 daright.
def twoSumSorted(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left, right]
if total < target:
left += 1 # need a bigger sum
else:
right -= 1 # need a smaller sum
return []
Trappole e casi limite
Il ciclo a due puntatori è breve, quindi gli errori si nascondono nei dettagli che lo circondano.
- Restituire posizioni con base 1. Questa versione richiede indici con base 0: per
[-4, 1, 3, 8, 12]etarget = 9la risposta è[1, 3], non[2, 4]. In Lua e R, sottrai 1 prima di restituire il risultato. - Usare il ciclo con
left <= right. Quando i puntatori si incontrano, la somma userebbe due volte lo stesso valore. - Spostare il puntatore sbagliato. Una somma troppo piccola richiede un valore più grande, e solo
leftpuò fornirlo. - Rifiutare i valori duplicati.
[2, 2, 5, 7]contarget = 4usa entrambi i 2, che si trovano in posizioni diverse. - Overflow. I limiti qui mantengono ogni somma entro un intero a 32 bit. Se i valori potessero arrivare a
10^9, sommali usando un tipo a 64 bit.
Domande frequenti4
Perché due puntatori funzionano per Two Sum su un array ordinato?
Quando la somma dei due estremi è troppo piccola, il valore a sinistra è troppo piccolo per ogni possibile compagno ancora in gioco, perché l'estremo destro è il più grande tra questi. Puoi eliminarlo definitivamente. Lo stesso ragionamento permette di eliminare il valore a destra quando la somma è troppo grande. La coppia corretta non viene mai eliminata, quindi i puntatori finiscono su di essa.
Qual è la complessità temporale di Two Sum II?
La soluzione con due puntatori viene eseguita in tempo O(n) e usa O(1) spazio aggiuntivo: a ogni passaggio un puntatore si sposta verso l'interno e i due si incontrano dopo al massimo n-1 passaggi. Cercare con la ricerca binaria ogni elemento corrispondente richiede O(n log n), mentre controllare ogni coppia richiede O(n²).
Perché non usare una mappa hash come nel primo Two Sum?
Una mappa hash funziona e viene eseguita in tempo O(n), ma memorizza fino a n valori. L’ordinamento rende superflua questa memoria: i due puntatori sanno in quale direzione spostarsi basandosi solo sulla somma. Gli intervistatori chiedono questa versione per vedere se sfrutti l’ordinamento che ti è stato fornito.
Quando la ricerca binaria è la scelta migliore in questo caso?
Quando un valore è fisso e ti serve solo il suo abbinamento. Se numbers[0] deve essere nella coppia, una ricerca binaria trova l’altro indice in O(log n). Per trovare una coppia sconosciuta, la scansione con due puntatori è più veloce di n ricerche separate.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def twoSumSorted(numbers, target):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
numbers = [-4, 1, 3, 8, 12] target = 9
Atteso
[1, 3]