javascript - 如何减少 0(n) 以找到求和特定值的对的第一个实例

Question

我在做一个codewars问题，说明如下:给定一个整数列表和一个总和值，返回前两个值(请从左边开始解析)按出现顺序加起来形成总和.

该解决方案有效，但对于长数组来说太慢了，如果不使用两个 for 循环，有人会怎么做呢？我一直在努力降低时间复杂度，但是当我需要查看所有可能的对时，我不知道如何实现这一点。

function sumPairs(ints, s){
    var lowestIdx1 = Infinity;
    var lowestIdx2 = Infinity;

    for (var i = 0; i < ints.length-1; i++) {
        var cur = ints[i]
        for (var k = i+1; k < ints.length; k++) {
            var next = ints[k]
            if(cur + next === s){
                if(i <= lowestIdx1 && k <= lowestIdx1 || i <= lowestIdx2 && k <=lowestIdx2){
                    lowestIdx1 = i
                    lowestIdx2 = k
                }
            }
        }
    }
    if(lowestIdx1 !== Infinity){    
        return [ints[lowestIdx1], ints[lowestIdx2]]
    }
}

为了更清楚地了解这里的问题，这里有一些示例输入输出:

sum_pairs([11, 3, 7, 5],         10)
#              ^--^      3 + 7 = 10
== [3, 7]

sum_pairs([4, 3, 2, 3, 4],         6)
#          ^-----^         4 + 2 = 6, indices: 0, 2 *
#             ^-----^      3 + 3 = 6, indices: 1, 3
#                ^-----^   2 + 4 = 6, indices: 2, 4
#  * entire pair is earlier, and therefore is the correct answer
== [4, 2]

sum_pairs([0, 0, -2, 3], 2)
#  there are no pairs of values that can be added to produce 2.
== undefined

Answer 1

你可以使用一些加速机制，比如

• 单循环，
• 访问值的哈希表
• 变量 a 用于元素 array[i]

一长串Sum of Pairs on Codewars需要 153 毫秒。

var sum_pairs = function (array, s) {
    var a, i,
        hash = Object.create(null);

    for (i = 0; i < array.length; i++) {
        a = array[i];
        if (hash[s - a]) {
            return [s - a, a];
        }
        if (!hash[a]) {
            hash[a] = true;
        }
    }
};

console.log(sum_pairs([11, 3, 7, 5], 10));        // [3, 7]
console.log(sum_pairs([4, 3, 2, 3, 4], 6));       // [4, 2]
console.log(sum_pairs([0, 0, -2, 3], 2));         // undefined
console.log(sum_pairs([10, 5, 2, 3, 7, 5], 10));  // [3, 7]
console.log(sum_pairs([1, 2, 3, 4, 1, 0], 2));    // [1, 1]
console.log(sum_pairs([1, -2, 3, 0, -6, 1], -6)); // [0, -6]
console.log(sum_pairs([0, 2, 0], 0));             // [0, 0]
console.log(sum_pairs([5, 9, 13, -3], 10));       // [13, -3]

.as-console-wrapper { max-height: 100% !important; top: 0; }