Le problème Two Sum en Python
Dans cette leçon, vous allez résoudre le problème Two Sum en trouvant deux éléments dont la somme vaut une valeur donnée, en un seul parcours de la liste.
Introduction
Le problème
Avec une liste de prix et un budget, quels deux articles coûtent exactement le budget ? Vérifier chaque paire marche mais demande environ n² / 2 comparaisons. Se souvenir de ce qu'on a déjà vu permet de le faire en un seul passage.
Imaginez-le ainsi
Two Sum, c'est comme faire ses courses avec un budget exact. Pour chaque étiquette, vous calculez la somme qui manque encore, puis vous regardez vos notes : ai-je déjà vu un article à exactement ce prix ? Si oui, la paire est trouvée. Sinon, vous notez ce prix et l'endroit où vous l'avez vu, et vous continuez.
complement = target - value🤔 Le prix qui manque encoreif complement in seen:📋 Ce prix est-il déjà dans mes notes ?return [seen[complement], index]🛍️ Paire trouvée : les deux positionsseen[value] = index✍️ Noter ce prix et sa position, puis continuerLe problème Two Sum demande les positions de deux nombres d'une liste dont la somme vaut une cible ; un dictionnaire des valeurs vues le résout en un seul passage, en temps O(n).
Points clés
complement = target - valueest la valeur qui compléterait la paire.seenassocie chaque valeur déjà visitée à son indice, donc les recherches sont rapides.if complement in seen:trouve le partenaire parmi les valeurs précédentes.seen[value] = indexest enregistré après le test, donc une valeur n'est jamais associée à elle-même.- Pour 9, la valeur 7 trouve son partenaire 2 à l'indice 0, ce qui donne
[0, 1].
Quand l’utiliser ?
- Trouver des paires de somme ou de différence donnée.
- Apprendre à échanger de la mémoire contre de la vitesse avec une table de hachage.
- Une question d'entretien très courante, base de 3-Sum et de problèmes similaires.
Quand s'en passer
- Une entrée triée avec peu de mémoire : deux pointeurs partant des deux bouts n'utilisent aucune mémoire en plus.
- Vous voulez toutes les paires, pas une seule : rassemblez les résultats au lieu de revenir à la première correspondance.
Code d’exemple
def two_sum(values, target):
seen = {}
for index, value in enumerate(values):
complement = target - value
if complement in seen:
return [seen[complement], index]
seen[value] = index
return []
print(two_sum([2, 7, 11, 15], 9))
Résultat de l’exécution
[0, 1]
Explication du code
Le dictionnaire seen enregistre les valeurs déjà parcourues avec leur position. Pour chaque élément, le programme calcule le complément complement = target - value et vérifie s'il se trouve déjà dans seen. Comme une recherche dans un dictionnaire coûte O(1), l'algorithme complet s'exécute en O(n) avec O(n) mémoire supplémentaire.
Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.
Exercices d’approfondissement
Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.
- Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
- Affichez l’état après chaque étape pour observer l’algorithme en action.
- Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Erreurs fréquentes
Enregistrer avant de tester
Une valeur peut s'associer à elle-même, comme 3 + 3 = 6 avec un seul 3.
seen[value] = index
if target - value in seen:
if target - value in seen:
return [seen[target - value], index]
seen[value] = index
Leçon terminée ?
Marquez-la comme apprise pour suivre votre progression.
S'entraîner avec un défi
Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.
Tous les défis