how to reduce 0(n) for finding the first instance of pairs that sum specific value

Question

I am doing a codewars problem, the instructions are as follows: Given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that add up to form the sum.

The solution works, but it is too slow for long arrays, how would someone do this without using two for loops? I have been trying to reduce the time complexity, but I am at a loss at how to accomplish this when I need to look at all possible pairs.

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]]
    }
}

To be more clear on the problem here are some sample input outputs:

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

The solution below runs in O(n) time, check out the steps for how it was solved:

// steps
// loop through array
// for each member
// first check if it's value in hash
// then store in hash with key as sum-member
// and value as member
// if value in hash already
// return [k,v]

function sumPairs(ints, s) {

  const possible_pairs={}

  // loop through array
  for(let ints_i=0;ints_i<ints.length;ints_i+=1){

    // for each member
    let element = ints[ints_i].toString()

    // first check if it's value in hash
    // if value in hash already
// return [k,v]
    if (possible_pairs[element]) return [parseInt(possible_pairs[element], 10), parseInt(element, 10)]

      // else store in hash with key as value-member
  // and value as member
    possible_pairs[s-element]=element
  }

  return undefined ;
}
console.log(sumPairs([ 0, -6], -6)) //[0, -6]
console.log(sumPairs([10, 5, 2, 3, 7, 5], 10)) //[3, 7]

Answer 2

You could use some speeding mechanisms, like

• single loop,
• hash table for visited values
• variable a for element array[i]

Long list of Sum of Pairs on Codewars needs 153 ms.

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