Maison > interface Web > js tutoriel > LeetCode : problème à deux sommes

LeetCode : problème à deux sommes

DDD
Libérer: 2024-12-13 07:24:12
original
887 Les gens l'ont consulté

LeetCode: twoSum Problem

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]
Copier après la connexion

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 = {}
}
Copier après la connexion

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
  }
}
Copier après la connexion

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]]
    }
  }
}
Copier après la connexion

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
  }
}
Copier après la connexion

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]

Copier après la connexion

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!

source:dev.to
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal