在数组中查找两个合计为所提供值的元素的更好算法

Question

我正在编写一个算法，用于在一个数组中查找两个元素，该元素的总和为所提供的值。也就是说，对于数组[2, 7, 5, 3, 4, 11, 12, 56]和值9，我找到了两个元素，例如。2和7，这增加了我们提供的值9。我将以[ [ 2, 7 ], [ 4, 5 ] ]的身份获得最终结果。请找到下面的代码

const getSumOfValuesInArr = (arr, val) => {
var result = [];
for (var i = 0; i < arr.length; i++) {
    for (var j = i; j < arr.length; j++) {
    if (arr[j] + arr[i] === val) {
        result.push([arr[i], arr[j]]);
    }
    }
}
console.log(result);
return result;
};

getSumOfValuesInArr([2, 7, 5, 3, 4, 11, 12, 56], 9);

但正如你所能做到的，它有点贵。如何编写更好的算法以获得更好的性能？请帮帮忙。

Answer 1

您可以采用单个循环，并将看到的值存储在哈希表中。

然后检查之前是否看到了所需总和和实际值的增量，然后将该对添加到结果集中。

​

const getSumOfValuesInArr = (arr, val) => {
    var result = [],
        seen = {};

    for (let i = 0; i < arr.length; i++) {
        if (seen[val - arr[i]]) result.push([val - arr[i], arr[i]]);
        seen[arr[i]] = true;
    }

    return result;
};

console.log(getSumOfValuesInArr([2, 7, 5, 3, 4, 11, 12, 56], 9));

​