Algorithmes Python

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.

  • Intermédiaire
  • 2 min de lecture
  • 1 exemple exécutable

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.

Des courses avec un budget au code
complement = target - value🤔 Le prix qui manque encore
if complement in seen:📋 Ce prix est-il déjà dans mes notes ?
return [seen[complement], index]🛍️ Paire trouvée : les deux positions
seen[value] = index✍️ Noter ce prix et sa position, puis continuer
Cherchez le prix manquant au lieu de tester toutes les paires.
En une phrase

Le 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

  1. complement = target - value est la valeur qui compléterait la paire.
  2. seen associe chaque valeur déjà visitée à son indice, donc les recherches sont rapides.
  3. if complement in seen: trouve le partenaire parmi les valeurs précédentes.
  4. seen[value] = index est enregistré après le test, donc une valeur n'est jamais associée à elle-même.
  5. 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

Exécuter le code →
main.py
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))
Obtenir un bouton Run pour cet exemple

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.

  1. Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
  2. Affichez l’état après chaque étape pour observer l’algorithme en action.
  3. Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Exécuter dans le compilateur Python →

Erreurs fréquentes

Enregistrer avant de tester

Une valeur peut s'associer à elle-même, comme 3 + 3 = 6 avec un seul 3.

Problème
seen[value] = index
if target - value in seen:
Correction
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