Two Sum
Hai un elenco di numeri interi e un valore obiettivo. Esattamente due numeri dell’elenco hanno una somma pari all’obiettivo, e il tuo compito è indicare le posizioni in cui si trovano.
Considera nums = [3, 8, 12, 5] e target = 17. Il valore 12 si trova all’indice 2 e 5 si trova all’indice 3, e 12 + 5 = 17, quindi la risposta è [2, 3].
I due numeri devono provenire da due posizioni diverse. In [4, 2, 6] con target = 8, non è consentito usare il 4 due volte; la risposta è [1, 2] perché 2 + 6 = 8. Tuttavia, lo stesso valore può comparire due volte: in [7, 3, 7] con target = 14 la risposta è [0, 2].
Scrivi una funzione chiamata twoSum che riceve un array di interi nums e un intero target, e restituisce un array di due indici [i, j] tali che nums[i] + nums[j] sia uguale a target.
Gli indici devono corrispondere a due posizioni diverse ed essere restituiti in ordine crescente (i minore di j). Ogni input ha esattamente una coppia di questo tipo.
Vincoli: 2 ≤ nums.length ≤ 10^4, -10^9 ≤ nums[i] ≤ 10^9, -10^9 ≤ target ≤ 10^9.
Funzione
- arg1integer-array
- arg2integer
- Restituisceinteger-array
Esempi
- Input
- arg1 = [3, 8, 12, 5]arg2 = 17
- Output
- [2, 3]
- Input
- arg1 = [6, 1, 4, 10]arg2 = 7
- Output
- [0, 1]
- Input
- arg1 = [2, -6, 9, 4, 13]arg2 = 3
- Output
- [1, 2]
+13 test nascosti all’invio
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 verifiche. 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 l’elenco una volta e mantieni una mappa hash che associ ogni valore già incontrato al 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 impedisce a un numero di essere abbinato a se stesso.
Presto una spiegazione completa di questo problema.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def twoSum(nums, target):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
arg1 = [3, 8, 12, 5] arg2 = 17
Atteso
[2, 3]