Two Sum
Tu reçois une liste de nombres entiers et une valeur cible. Exactement deux nombres de la liste ont pour somme la valeur cible, et ton travail consiste à indiquer leurs positions.
Prends nums = [3, 8, 12, 5] et target = 17. La valeur 12 se trouve à l’indice 2 et 5 à l’indice 3, et 12 + 5 = 17, donc la réponse est [2, 3].
Les deux nombres doivent provenir de deux positions différentes. Dans [4, 2, 6] avec target = 8, il n’est pas permis d’utiliser le 4 deux fois ; la réponse est [1, 2], car 2 + 6 = 8. La même valeur peut toutefois apparaître deux fois : dans [7, 3, 7] avec target = 14, la réponse est [0, 2].
Écris une fonction nommée twoSum qui reçoit un tableau d’entiers nums et un entier target, et renvoie un tableau de deux indices [i, j] tels que nums[i] + nums[j] soit égal à target.
Les indices doivent correspondre à deux positions différentes et être renvoyés dans l’ordre croissant (i inférieur à j). Chaque entrée possède exactement une telle paire.
Contraintes : 2 ≤ nums.length ≤ 10^4, -10^9 ≤ nums[i] ≤ 10^9, -10^9 ≤ target ≤ 10^9.
Fonction
- arg1integer-array
- arg2integer
- Renvoieinteger-array
Exemples
- Entrée
- arg1 = [3, 8, 12, 5]arg2 = 17
- Sortie
- [2, 3]
- Entrée
- arg1 = [6, 1, 4, 10]arg2 = 7
- Sortie
- [0, 1]
- Entrée
- arg1 = [2, -6, 9, 4, 13]arg2 = 3
- Sortie
- [1, 2]
+13 tests cachés à la soumission
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Essayer chaque paire avec deux boucles imbriquées est correct, mais pour 10 000 nombres, cela représente environ 50 millions de vérifications. Peux-tu trouver le partenaire de chaque nombre sans parcourir à nouveau la liste ?
Lorsque vous vous trouvez sur une valeur
x, vous savez déjà quelle valeur compléterait la paire : la cible moinsx. La seule question est de savoir si vous avez déjà rencontré cette valeur, et à quel indice.Parcours la liste une seule fois et conserve une table de hachage associant chaque valeur déjà parcourue à son index. À chaque position, recherche d’abord le complément manquant ; s’il se trouve dans la table, tu as les deux indices. Sinon, enregistre la valeur actuelle et passe à la suite. C’est le fait de rechercher avant d’enregistrer qui empêche un nombre de former une paire avec lui-même.
Une explication complète de ce problème arrive bientôt.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
Python
def twoSum(nums, target):
# Écrivez le code iciCas 1
Cas 2
Cas 3
Entrée
arg1 = [3, 8, 12, 5] arg2 = 17
Attendu
[2, 3]