我的嵌套for循环在一个数组中搜索2个加起来就是一个和值的数字时超时

Question

我试图找到一种更好/更快的算法，当我试图在一个数字数组中找到任何2个加起来就是一个和的数字(例如s(时，该算法不会超时。我需要返回一对加起来就是sum的数字，它们也有最早出现的索引(可能还有很多其他对(。这是我的嵌套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)，请创建一个Set。在对一个数字进行迭代时，检查该集合是否具有值sum - num——如果具有，则返回该对作为结果。否则，将数字放入集合：

或者你可以使用Set

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));