Deux sommes pour une cible

Pour chaque élément $x$ du tableau, son complémentaire recherché est $y=\text{cible}-x$. On conserve l'historique des valeurs déjà rencontrées dans un dictionnaire :

def deux_sommes(t: list, cible: float) -> bool:
    vus = {}
    for x in t:
        # Invariant : vus contient exactement les valeurs de t[0..i-1] rencontrées
        partenaire = cible - x
        if partenaire in vus:
            return True
        vus[x] = True
    return False

Chaque itération effectue une recherche et une insertion en $O(1)$ dans le dictionnaire vus. La complexité totale est donc linéaire $O(n)$.