How to decrease 0 (n) to find the first instance of pairs that sum to a specific value
I am making a problem with code machines, the following instructions: Given a list of integers and one 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's too slow for long arrays, how would someone do it without using two loops? I've tried to reduce the time complexity, but I don't understand how to do 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]]
}
}
For a clearer understanding of the problem, here's some input output:
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
+3
source to share
1 answer
You can use some acceleration mechanisms like
- single cycle,
- hash table for visited values
- variable
a
for elementarray[i]
A long list Amount pairs per code channel requires 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; }
+2
source to share