Problème — Deux nombres de somme donnée

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 $\text{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