Deux sommes pour une cible

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 2 — Recherche séquentielle et dictionnaires

Énoncé

Écrire une fonction deux_sommes(t, cible) déterminant s'il existe deux indices distincts $i \neq = j$ tels que t[i] + t[j] == cible, avec une complexité temporelle de $O (n)$ .

Corrigé

Pour chaque élément $x$ du tableau, son complémentaire recherché est $y = 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)$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.