Deux Somme (Two Sum)
Dictionnaires
Enonce
Écrire une fonction qui prend une liste d'entiers L et un entier cible, et renvoie un tuple (i, j) avec i < j tels que L[i] + L[j] == cible. Si aucune paire n'existe, renvoyer (-1, -1).
deux_somme([2, 7, 11, 15], 9) → (0, 1) deux_somme([3, 2, 4], 6) → (1, 2) deux_somme([1, 2, 3], 10) → (-1, -1)
Signature attendue
def deux_somme(L: list, cible: int) -> tuple:Exemples
deux_somme([2, 7, 11, 15], 9)→(0, 1)deux_somme([3, 2, 4], 6)→(1, 2)deux_somme([1, 2, 3], 10)→(-1, -1)
Dictionnaire comme table de hachage
En utilisant un dictionnaire comme table de correspondance valeur → indice, on peut résoudre le problème Two Sum en un seul parcours O(n) au lieu de la double boucle naïve O(n²). Pour chaque élément, on vérifie si son complément est déjà dans le dictionnaire.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Produit Matriciel
- Inverser un Dictionnaire
- Regrouper par Valeur
- Histogramme de Mots
- Cache LRU Simplifié
- Diagonale Principale
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.