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 < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      console.log(` i is ${nums[i]} and k is ${nums[j]}`)
      // lets check if we add the 2 numbers if it equals target
      if (target === nums[i] + nums[j]) {
        return [i, j]
      }
    }
  }
};

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target));

Approche 1 Complexité

La complexité temporelle est O(n²)

1. Boucles imbriquées vérifiant chaque paire de nombres
2. Vérifie toutes les combinaisons possibles
3. Devient très lent avec les grands tableaux

La

La complexité spatiale est O(1)
1.Nous n'avons créé aucune nouvelle structure de données

Approche 2 Plus efficace et ce que nous voulons.

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

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

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

const twoSumOptimizedRegularObject = (nums, target) => {
  const objectStuff = {}

  // write a for loop, to go through the arr
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i] 

    if (complement in objectStuff) {
      return [objectStuff[complement],i]
    }
    objectStuff[nums[i]] = i 
  }
}

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSumOptimizedRegularObject(nums, target));

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.

const twoSumOptimized = (nums, target) => {
  const mapOfStuff = new Map()

  // write a for loop, to go through the arr
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i]

    if (mapOfStuff.has(complement)) {
      return [mapOfStuff.get(complement), i]
    }
    mapOfStuff.set(nums[i], i)
  }

}

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSumOptimized(nums, target));

Approche 2 Complexité

La complexité temporelle est O(n)

1. Un seul passage à travers le tableau
2. La carte de hachage fournit une recherche O(1)
3. Le temps total évolue linéairement avec la taille du tableau

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

Mises en garde

1. Tableau vide
2. Aucune solution n'existe
3. Plusieurs solutions sont possibles. Dans ce cas, demandez si vous revenez après la première itération.

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!