K – Paires complémentaires avec JavaScript

J’ai récemment eu l’occasion de relever un défi de code pour une entreprise que j’admire vraiment et avec laquelle j’aimerais travailler un jour. J’étais reconnaissant, excité et encore plus anxieux parce qu’il y avait beaucoup d’inconnues dans le défi du code. La réalité est qu’il n’y a que tant de choses que vous pourriez faire pour vous préparer:

• Projets de construction
• Algorithmes d’étude
• Problèmes de mouture: LeetCode, HackerRank, CodeSignal

Cependant, la seule façon de savoir si vous êtes prêt ou non est de sauter dans les profondeurs pour voir si vous pouvez flotter. C’est ce que j’ai fait, et j’ai appris tellement plus que jamais auparavant, et à cause de cela, je voulais le partager.

Au début de la mission, j’avais trois tâches à accomplir. Je vais me concentrer sur seulement 1 d’entre eux dans ce blog — K – Paires complémentaires.

L’objectif

• On vous donne un Entier cible et un tableau plein d’entiers positifs
• Vous devez trouver et localiser le complément de l’Entier Cible — ce qui signifie que la valeur d’un index et d’un autre index DOIT être égale à la Cible
• Retourne le compte des paires à la fin

numberArray + numberArray = 7

Ce qui précède serait une paire valide puisque ces deux valeurs sont égales à la cible.

Première approche

Lorsque j’ai abordé ce problème pour la première fois, je l’ai poursuivi de manière brutale. Je pensais pouvoir utiliser des boucles imbriquées pour vérifier les paires complémentaires, et bon, j’avais raison! Cela a réellement fonctionné:

Comment ça marche ?

• Vous bouclez les éléments du tableau initial.
• Vous le survolez ensuite à l’unisson pour vérifier s’il est égal ou non à la cible à chaque passage.
• Si la cible correspond, le nombre est incrémenté.

Bien que cela fonctionne, et que j’ai reçu un décompte précis des paires complémentaires données à une cible, ce n’était pas idéal. La réalité est que les boucles imbriquées sont lentes et peuvent croître de manière exponentielle compte tenu de tableaux d’éléments plus grands. La complexité temporelle pour cela est O(N2).

Deuxième Approche – Optimisation

Je suis donc retourné à la planche à dessin. Après quelques recherches et réflexions, j’ai constaté que je pouvais stocker les valeurs dans un objet — {key: value}.

Maintenant, c’était encore très délicat, d’autant plus que je n’avais jamais écrit quelque chose d’aussi complexe auparavant. Je marchais sur un nouveau territoire, mais j’étais excité car j’étais en mesure d’optimiser mon ancien algorithme en O(N):

Alors, comment cela fonctionne-t-il?

• Vérifiez que le nombre ou la longueur est existant.
• Nous parcourons d’abord le numberArray pour créer des paires clé/valeur dans l’objet located_pairs. Tout au long de ce processus, il vérifiera l’unicité et les doublons.
• Nous passons ensuite en revue les clés de l’objet localisé et vérifions s’il fait ou non avec la cible. Si c’est le cas, le nombre de paires est incrémenté.