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
[[7,2,4,1],6][[3,4],6][[3,3],6][[],5][[5],5][[0,0],0]
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.