Two Sum

Q: Quelle est la complexité temporelle de Two Sum ?

La solution avec table de hachage s’exécute en O(n) temps, car elle parcourt chaque nombre une seule fois et que chaque recherche ou insertion prend un temps constant en moyenne. Elle utilise un espace supplémentaire de O(n) pour la table. Vérifier chaque paire prend O(n²) temps et O(1) espace.

FacileHachage

+10

Vous recevez un tableau d’entiers nums et un entier target. Exactement deux éléments de nums, situés à deux positions différentes, ont une somme égale à target. Renvoyez les indices de ces deux éléments, le plus petit indice en premier.

Fonction

twoSum(nums: integer-array, target: integer) → integer-array

numsinteger-array: le tableau d’entiers dans lequel effectuer la recherche
targetinteger: la somme que les deux entrées doivent atteindre
Renvoieinteger-array: les deux indices, le plus petit en premier

Contraintes

2 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
-10⁹ ≤ target ≤ 10⁹
Il existe exactement une paire de positions distinctes dont la somme est égale à target.

Exemples

Entrée: nums = [3, 8, 12, 5]target = 17
Sortie: [2, 3]
Explication: 12 se trouve à l’indice 2 et 5 à l’indice 3, et 12 + 5 = 17. Aucune autre paire n’atteint 17.

Pour aller plus loin

Si nums était déjà trié, pourrais-tu trouver la paire en O(n) temps avec seulement O(1) mémoire supplémentaire ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Vérifier chaque paire fonctionne, mais le travail augmente avec le carré de la longueur. Inverse la question : en partant d’un nombre x, tu sais déjà que son partenaire doit être target - x. Une table de hachage te permet de savoir en temps constant si tu es déjà passé par cette valeur, donc un seul parcours suffit.

Vérifiez chaque paire

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Fixe un premier indice i et essaie chaque indice j à sa droite jusqu’à ce que nums[i] + nums[j] soit égal à target. Commencer j à i + 1 empêche une position de s’associer à elle-même, essaie chaque paire une seule fois et place le plus petit indice en premier. La paire recherchée fait partie des paires que tu essaies, donc tu la trouveras.

n nombres forment environ n²/2 paires : n = 10^4 signifie près de 5 × 10^7 additions.

Algorithme

Parcourez chaque indice de nums avec i.
Pour chaque i, parcourez les indices à partir de i + 1 jusqu'au dernier indice avec j.
Si nums[i] + nums[j] est égal à target, renvoyez [i, j].
Si les deux boucles se terminent, renvoyez un tableau vide. L'énoncé garantit que cela ne se produit jamais.

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 passage avec une table de hachage

Intuition

Pour un nums[i] donné, la boucle interne de la méthode par force brute cherche une valeur que tu connais à l’avance : target - nums[i]. Cette recherche est en fait une consultation, et une table de hachage associant chaque valeur à un indice permet d’effectuer des consultations en temps constant en moyenne.

Consulte d’abord, stocke ensuite. Ainsi, un nombre ne peut être associé qu’à un nombre qui le précède, jamais à lui-même, et comme le nombre associé est toujours antérieur, son indice vient en premier. Chaque nombre est parcouru une seule fois, avec des opérations sur la table en temps constant ; la recherche est donc en O(n), au prix d’une table pouvant contenir jusqu’à n entrées.

Algorithme

Créez une map vide associant chaque valeur à son index.
Pour chaque index i, calculez need, la valeur qui complète la paire : target moins nums[i].
Si need se trouve dans la map, renvoyez son index enregistré, suivi de i.
Sinon, enregistrez nums[i] avec l’index i et continuez.

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 []

Pièges et cas limites

Stocker un nombre avant de chercher son complément. Avec [4, 2, 6] et target = 8, le 4 se trouve lui-même et tu renvoies [0, 0].
Renvoyer les indices dans le mauvais ordre. Lorsque la recherche précède le stockage, l’indice de la map est le plus petit et vient en premier.
Trier le tableau pour utiliser deux pointeurs, puis renvoyer les positions dans la copie triée. Conserve l’indice d’origine à côté de chaque valeur.
Supposer que les valeurs sont positives ou distinctes. [0, 7, -3, 0] avec target = 0 associe les deux zéros : [0, 3].
En Lua et en R, renvoyer les indices à base 1. Soustrais 1 à chacun.

Questions fréquentes3

Quelle est la complexité temporelle de Two Sum ?

La solution avec table de hachage s’exécute en O(n) temps, car elle parcourt chaque nombre une seule fois et que chaque recherche ou insertion prend un temps constant en moyenne. Elle utilise un espace supplémentaire de O(n) pour la table. Vérifier chaque paire prend O(n²) temps et O(1) espace.

Peut-on résoudre Two Sum sans espace supplémentaire ?

Pas en temps linéaire sur un tableau non trié. Avec un espace supplémentaire de O(1), tu dois vérifier chaque paire, ce qui prend O(n²). La table de hachage échange une mémoire de O(n) contre un temps linéaire.

Comment Two Sum gère-t-il les nombres en double ?

Les doublons fonctionnent quand tu recherches le nombre complémentaire avant de stocker le nombre actuel. Dans [7, 3, 7] avec target = 14, le premier 7 est stocké à l’index 0 et le second 7 le trouve, ce qui donne [0, 2]. Un 7 isolé ne peut jamais être associé à lui-même : il ne se trouve pas encore dans la map au moment où tu le recherches.

def twoSum(nums, target):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

nums = [3, 8, 12, 5]
target = 17

Résultat attendu

[2, 3]