Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › Deux montants, sans tri

Deux montants, sans tri

Exercice de la série « Maps, Sets et regroupements »debutant

Le problème. Le même que sur un tableau trié, mais cette fois les montants arrivent dans un ordre quelconque. On veut deux montants distincts dont la somme fait la cible.

Écrivez deuxSommes(montants, cible) qui renvoie les deux positions dans l'ordre croissant, ou null si aucune paire ne convient.

Appel Résultat attendu
deuxSommes([7, 2, 4, 1], 6) [1, 2]
deuxSommes([3, 4], 6) null — un seul 3, on ne l'additionne pas à lui-même
deuxSommes([3, 3], 6) [0, 1]
deuxSommes([], 5) null
deuxSommes([5], 5) null

Ce qu'on attend. La double boucle est en O(n²). Il existe une réponse en un seul parcours : pensez à ce qu'une table de hachage vous fait gagner sur la question « ai-je déjà vu le complément ? ».

Le piège. L'ordre entre « mémoriser » et « interroger » décide de tout. Mal placé, il fait apparier un montant avec lui-même.

Cas de test

Écrire le code et le faire exécuter →

Votre code s'exécute réellement dans le navigateur, et la correction compare son résultat à celui d'une solution de référence.

La leçon qui prépare cet exercice

Les autres exercices de « Maps, Sets et regroupements »