Problème — Deux nombres de somme donnée

Dictionnaires et tables de hachage · niveau 3 (difficile)

Énoncé

Problème — Deux nombres de somme donnée.

On dispose d'une liste d'entiers et d'une valeur cible. Déterminer s'il existe deux éléments dont la somme vaut la cible, et renvoyer leurs indices.

Corrigé

Une approche naïve teste toutes les paires en $O (n^{2})$ . En mémorisant dans un dictionnaire les valeurs déjà vues (associées à leur indice), on résout le problème en un seul passage : pour chaque élément $x$ , on cherche si le complément $cible - x$ a déjà été rencontré. Chaque test coûte $O (1)$ en moyenne, d'où un coût total $O (n)$ .


def somme_cible(liste, cible):
    vus = {}                       # valeur -> indice
    for i, x in enumerate(liste):
        complement = cible - x
        if complement in vus:
            return (vus[complement], i)
        vus[x] = i
    return None

print(somme_cible([2, 7, 11, 15], 9))   # (0, 1)
print(somme_cible([3, 2, 4], 6))        # (1, 2)
print(somme_cible([1, 2, 3], 100))      # None