在数组中搜索 2 个数字总和值时，我的嵌套 for 循环超时

Question

我试图找到一个 better/faster 算法，当我试图在数字数组中找到任何 2 个数字加起来等于一个总和（例如 s）时，该算法不会超时。我需要 return 加起来为 sum(s) 的一对数字，它们也有最早出现的索引（可能还有许多其他对）。这是我的嵌套 for 循环方法。

function sum(ints, s){
  let pusher = [];
  let count = 1000;
  for(let i = 0; i < ints.length; i++){
      for(let j = i+1; j < ints.length; j++){
        if(ints[i] + ints[j] === s){
          if(j < count){
            pusher = [ints[i],ints[j]];
            count = j;  
          }
        } 
    }
  }
  return pusher.length > 0 ? pusher : undefined ;
}

Answer 1

要将计算复杂度从 O(n ^ 2) 降低到 O(n)，请改为创建一个集。迭代一个数字时，检查集合是否具有值 sum - num - 如果有，则 return 该对作为结果。否则，将数字放入集合中：

或者您可以使用集合

function sum(ints, sum) {
  const set = new Set();
  for (const num of ints) {
    const otherNum = sum - num;
    if (set.has(otherNum)) {
      return [num, otherNum];
    } else {
      set.add(num);
    }
  }
}
console.log(sum([3, 4, 99, -2, 55, 66, -3], 1));
console.log(sum([1, 9, 15, 2, 4, 7, 5], 6));