LeetCode : problème à deux sommes

Le problème twoSum est un défi de codage classique qui teste vos compétences en résolution de problèmes et en algorithmique.

Dans cet article, nous examinerons d’abord une solution simple et facile à comprendre. Ensuite, nous l’optimiserons étape par étape pour améliorer son efficacité. Que vous débutiez en algorithmes ou que vous prépariez des entretiens, ce guide vous aidera à maîtriser le problème. Commençons !

let inputArray = [2, 7, 11, 15]
let target = 9
console.log(twoSum(inputArray, target)) // Output: [0, 1]

Regardons l'entrée et la sortie que la fonction doit gérer.

Étant donné le tableau [2,7,11,15] et une cible de 9, le résultat sera [0,1].

En effet, la somme des valeurs aux indices 0 et 1 donne 9, ce qui est la cible.

function twoSum(nums, target) {
  const hashMap = {}
}

Nous penserons à une solution où nous créons un hashMap pour stocker le numéro dans le tableau comme clé et son index comme valeur.

function twoSum(nums, target) {
  const hashMap = {}

  for (let i = 0; i < nums.length; i++) {
    hashMap[nums[i]] = i
  }
}

Voici la première partie de la solution : préparer le hashMap.

Dans la boucle suivante, on vérifie si le hashMap contient le complément de la cible moins le numéro actuel dans le tableau.

function twoSum(nums, target) {
  const hashMap = {}

  for (let i = 0; i < nums.length; i++) {
    hashMap[nums[i]] = i
  }

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]

    if (hashMap[complement] !== undefined && hashMap[complement] !== i) {
      return [i, hashMap[complement]]
    }
  }
}

Si le complément est trouvé dans le hashMap, on peut accéder à son index puisqu'on a sa valeur.

Ensuite, nous pouvons renvoyer un tableau contenant sa valeur (l'index du complément) ainsi que i, qui représente l'itération actuelle.

Dans cette solution, nous voyons que nous créons deux boucles distinctes. Nous pouvons les combiner en une seule boucle, économisant ainsi une itération.

function twoSum(nums, target) {
  const hashMap = {}

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]

    if (hashMap[complement] !== undefined && hashMap[complement] !== i) {
      return [i, hashMap[complement]]
    }
    hashMap[nums[i]] = i
  }
}

Nous avons affiné la condition pour une meilleure clarté et obtenu le code suivant :

function twoSum(nums, target) {
  const hashMap = {}

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]

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

let inputArray = [2, 7, 11, 15]
let target = 9
console.log(twoSum(inputArray, target)) // Output: [0, 1]

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!