LeetCode：二和问题

twoSum 问题是一个经典的编码挑战，测试您的问题解决和算法技能。

在这篇文章中，我们将首先看看一个易于理解的简单解决方案。然后我们会逐步优化它，提高它的效率。无论您是算法新手还是准备面试，本指南都将帮助您解决问题。让我们开始吧！

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

让我们看看函数应该处理的输入和输出。

给定数组 [2,7,11,15] 和目标 9，输出将为 [0,1].

这是因为索引 0 和 1 处的值加起来为 9，这是目标。

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

我们会想到一个解决方案，创建一个 hashMap 将数组中的数字存储为键，将其索引存储为值。

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

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

这是解决方案的第一部分：准备 hashMap。

在下一个循环中，我们检查 hashMap 是否包含目标减去数组中当前数字的补集。

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]]
    }
  }
}

如果在 hashMap 中找到补集，我们就可以访问它的索引，因为我们有它的值。

然后，我们可以返回一个包含其值（补集的索引）以及 i 的数组，i 代表当前迭代。

在此解决方案中，我们看到我们正在创建两个单独的循环。我们可以将它们组合成一个循环，从而节省一次迭代。

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
  }
}

我们改进了条件以获得更好的清晰度并获得以下代码：

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]

以上是LeetCode：二和问题的详细内容。更多信息请关注PHP中文网其他相关文章！