JavaScript 中的二和问题

我被问到的第一个技术问题是经典的二和算法问题。当时我对算法还很陌生，虽然能解决，但无法将其优化到所需的时间复杂度。事实证明，这是一个非常常见的问题，你很可能会在面试或以后练习算法时遇到它。

这是一种很有用的模式，它会在不同类型的问题中出现，所以如果它出现的话，最好知道如何解决它。

问题

因此，二和问题的一般思路是，你有一个数字列表或数组，以及一个目标和。你需要返回两个数字的索引，使它们相加后达到目标和。数字列表中应该只有一个解，并且一个数字不能重复使用。

我的第一个解决方案

假设输入是：

1. 数组 = [1, 3, 10, 11, 14]
2. 目标 = 13

const twoSum = (array, goal) => {
    let indexes = [];

    for(let i = 0; i < array.length; i++){
       for(let j = i + 1; j < array.length; j++){
          if (array[i] + array[j] === goal) {
        indexes.push(i);
        indexes.push(j);
          }
       }
    }
    return indexes;
}

这将返回一个数组 [1, 2]。

它可以工作，但如果你仔细检查一下，就会发现它在一个循环里套着另一个循环，来找出哪两个数加起来等于目标值。这使得时间复杂度达到了 O(n^2)。相当慢。对于像我们这样的小数组来说，这不算什么问题，但它远未达到优化水平。我可以毫不怀疑地说，如果你正在处理这类问题，他们会希望你改进时间复杂度。

更优化的解决方案

让我们假设相同的输入：

1. 数组 = [1, 3, 10, 11, 14]
2. 目标 = 13

const twoSum = (array, goal) => {
    let mapOfNumbers = {};
        let twoIndexes = [];

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

    for (let i = 0; i < array.length; i++) {
          let target = goal - arr[i];
      if(mapOfNumbers[target] !== null && mapOfNumbers[target] !== i) {
        twoIndexes.push(i);
            twoIndexes.push(mapOfNumbers[target]);
      }
        }

      return twoIndexes;
}

好的，让我们来讨论一下发生了什么。

首先，我映射了数字及其索引。我使用了第一个 for 循环来实现这一点。注意，我将数字指定为键，将索引指定为值。

第二件事是运行第二个循环遍历数组，首先确定在该索引处什么值必须等于目标。

然后在循环中，我使用 if 语句来检查两件事。一是检查目标值是否存在于我们创建的 map 中。二是确保它不与我们当前正在处理的索引相同。

如果它们都通过，那么我会将这两个索引推送到我的输出数组中并简单地返回它。

所以，虽然这个代码有两个循环，但它们不是嵌套的，所以时间复杂度降到了 O(n) 次方。好多了。

包起来

好了，今天就讲到这里，如果你还有任何问题，欢迎随时联系我。希望以上内容能帮助大家解决你未来肯定会遇到的问题。祝你编程愉快！