Problème à deux sommes en Javascript

Idée générale

Le problème Deux Sommes est un problème algorithmique classique. Il vous demande de trouver deux nombres dans un tableau dont la somme correspond à une *cible * spécifique fournie, puis de renvoyer leurs indices à partir du tableau donné.

Énoncé du problème

Étant donné un tableau de nombres entiers et une cible entière, renvoie les indices des deux nombres tels qu'ils s'additionnent jusqu'à la cible. Chaque entrée aura exactement une solution et vous ne pourrez pas utiliser deux fois le même élément.

Entrée : nums = [2, 7, 11, 15], cible = 9
Sortie : [0, 1]
Explication : nums[0] nums[1] = 2 7 = 9

Approche 1 Force brute

La première approche de tout problème pourrait simplement être de faire quelque chose et c'est la chose la plus simple sur le plan conceptuel.

Parcourez le tableau avec deux boucles et vérifiez toutes les paires de nombres.

const twoSum = (nums, target) => {
  for(let i = 0; i 



<h3>
  
  
  Approche 1 Complexité
</h3>

<p><strong>La complexité temporelle</strong> est <em>O(n²)</em></p>

<ol>
<li>Boucles imbriquées vérifiant chaque paire de nombres</li>
<li>Vérifie toutes les combinaisons possibles</li>
<li>Devient très lent avec les grands tableaux</li>
</ol>

La <p><strong>La complexité spatiale</strong> est <em>O(1)</em><br>
1.Nous n'avons créé aucune nouvelle structure de données</p>
<h2>
  
  
  Approche 2 Plus efficace et ce que nous voulons.
</h2>

<p>Nous utiliserons une carte de hachage pour résoudre ce problème. Expliquons un peu cet algorithme</p>

<ol>
<li>Nous utilisons une carte de hachage (objet en JavaScript) pour stocker les numéros que nous avons vus</li>
<li>Pour chaque nombre, on calcule son complément (cible - nombre actuel)</li>
<li>On vérifie si le complément existe dans notre carte</li>
<li>Si c'est le cas, nous avons trouvé nos deux nombres et renvoyé leurs indices</li>
<li>Sinon, nous ajoutons le numéro actuel à la carte</li>
</ol>

<p>La première solution pourrait donc consister à utiliser l'objet JS standard et à construire notre HashMap de cette façon<br>
</p>

<pre class="brush:php;toolbar:false">const twoSumOptimizedRegularObject = (nums, target) => {
  const objectStuff = {}

  // write a for loop, to go through the arr
  for (let i = 0; i 



<p>La deuxième solution utilise en fait la structure de données Map dans JS. Cela permet des implémentations plus strictes et plus robustes, en utilisant un objet Map (introduit dans ES6) et est souvent préférée. Une carte fournit un comportement de carte de hachage explicite et évite certaines bizarreries des objets JavaScript, comme l'héritage des propriétés d'Object.prototype.<br>
</p>

<pre class="brush:php;toolbar:false">const twoSumOptimized = (nums, target) => {
  const mapOfStuff = new Map()

  // write a for loop, to go through the arr
  for (let i = 0; i 



<h3>
  
  
  Approche 2 Complexité
</h3>

<p><strong>La complexité temporelle</strong> est <em>O(n)</em></p>

<ol>
<li>Un seul passage à travers le tableau</li>
<li>La carte de hachage fournit une recherche O(1)</li>
<li>Le temps total évolue linéairement avec la taille du tableau</li>
</ol>

<p><strong>La complexité spatiale</strong> est O(n)<br>
Dans le pire des cas, nous pourrions stocker presque tous les numéros<br>
Compromis entre temps et efficacité de la mémoire</p>

<h2>
  
  
  Mises en garde
</h2>

<ol>
<li>Tableau vide</li>
<li>Aucune solution n'existe</li>
<li>Plusieurs solutions sont possibles. Dans ce cas, demandez si vous revenez après la première itération.</li>
</ol>


          

            
        

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!