Leetcode : une approche intuitive à deux sommes

Imaginez-vous comme l'heureux propriétaire d'une boutique de souvenirs à l'intérieur du Spot-On Change Hotel. A la fermeture de la caisse, vous constatez un excédent de 8 euros. Il semble qu'un invité n'ait pas reçu la monnaie exacte. Cela pourrait ternir la réputation de l'hôtel. Pour éviter cela, vous décidez de résoudre le mystère du changement incorrect. En ouvrant le système de caisse de la boutique, vous découvrez que l'erreur s'est produite sur deux comptes différents !

Vous élaborez un plan : visiter chaque chambre et demander aux clients quelle monnaie ils ont reçue dans la boutique jusqu'à ce que vous trouviez les deux avec la mauvaise facture. En arrivant au premier étage, un client déclare avoir reçu 4 euros de monnaie. Vous calculez qu'il vous faut trouver un nombre qui, ajouté aux 4 euros, donne 8. En passant au deuxième étage, la monnaie du client est de 5 euros. 4 + 5 donne 9, donc ça ne peut pas être celui-là… Cinquième étage, sixième… Dixième, NON, NON, NON !

Comme vous n'avez pas trouvé la valeur du premier coup, vous descendez au deuxième étage et recommencez à demander à tous les invités leur monnaie afin de pouvoir la comparer avec la valeur de l'étage de départ suivant, épuisant, n'est-ce pas il? En informatique, cette méthode de recherche est appelée force brute, une méthode de recherche extrêmement lente qui fonctionne en comparant un élément avec les suivants dans le tableau.

Cela prend beaucoup de temps et n'est pas efficace, imaginez monter et descendre plusieurs fois tous les étages du Spot-On Change Hotel ! Ce n’est pas pratique pour vous ni pour l’ordinateur.

Si vous êtes curieux de savoir comment se dérouleraient ces montées et descentes d'étages dans un logiciel, cela ressemblerait à ceci en JavaScript :

 twoSum(nums, target) { for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] === target) { return [i, j]; } } } }

Après avoir évalué la situation sereinement, vous réalisez qu'il existe un moyen plus efficace de retrouver les deux invités avec la mauvaise monnaie.

Vous affinez votre intuition mathématique initiale selon laquelle 9 euros égale x + y. En appliquant un peu d'arithmétique, vous réalisez que : x + y = 9 revient à dire que y = 9 — x, et cela fait toute la différence pour augmenter l'efficacité de votre recherche.

Une autre chose qui a changé dans votre stratégie est que vous prendrez désormais un bloc-notes pour noter les valeurs que les invités vous disent, afin que vous n'ayez pas à demander deux fois la même valeur aux invités et que vous n'ayez pas à dépenser la journée à monter et descendre les escaliers. (Quel moment terrible pour que l'ascenseur tombe en panne !).

Muni des nouveaux outils, vous vous dirigez vers le premier étage, où un invité vous informe qu'il a 5 euros de monnaie. Vous enregistrez cela sous la forme {5 : 0}, indiquant une valeur de 5 à la position 0. En remplaçant x par 5 dans l'équation, vous calculez y = 8–5, ce qui donne y = 3. Puisque votre bloc-notes est toujours vide, vous ne ne faites pas enregistrer le chiffre 3, qui serait le chiffre complémentaire de 5 pour arriver au résultat 8. Vous notez ensuite le chiffre 5 sur votre bloc-notes (pensez à toujours noter le chiffre vérifié à l'instant et non son complément ; vous n'utilisera le complément que pour le comparer avec le nombre cible que vous aurez noté). Vous passez au deuxième invité, qui mentionne avoir reçu 2 euros de monnaie. En appliquant à nouveau la formule : y = 8–2 => y = 6, vous vérifiez votre enregistrement, où vous ne trouvez aucun chiffre 6. Ainsi, vous ajoutez le 2 à votre enregistrement, qui vaut désormais {5 : 0, 2 : 1}. En poursuivant la recherche, le prochain invité déclare avoir reçu 3 euros de monnaie. Vous calculez à nouveau : y = 8–3 => y = 5. Bingo ! Vous avez un 5 enregistré sur votre bloc-notes ! L'invité de l'étage 0 est complémentaire de celui de l'étage 2 ! Cette approche est connue sous le nom de table de hachage et elle est beaucoup plus rapide et efficace, tant pour vous que pour l'ordinateur. En JavaScript, cela serait implémenté comme suit :

 twoSum(nums, target) { const myTable = {}; for (let i = 0; i < nums.length; i++) { const complementaryNumber = target - nums[i]; if (complementaryNumber in myTable) { return [i, myTable[complementaryNumber]]; } myTable[nums[i]] = i; } }

Il s'agit d'un problème simple de Leetcode qui ne devient facile qu'une fois que vous avez compris les concepts qui le sous-tendent. Je vous recommande d'essayer de résoudre le problème par vous-même et de passer du temps à essayer de créer une intuition derrière celui-ci, de créer votre propre analogie, de réviser et d'essayer d'écrire du pseudocode avant de passer à la solution.

J'espère que mon analogie vous a aidé à mieux comprendre les concepts derrière le défi à deux sommes.

À la prochaine!