Solomon Bothwell - 1 year ago 104
Javascript Question

# solving the 2-sum algorithm in javascript

I'm trying to write a simple solution to the 2-Sum problem in Javascript. The problem goes: given an array of n integers and a target sum, determine what combinations of two integers will sum to the target value.

I found a few different language agnostic examples using hash tables and tried to come up with a solution in javascript:

``````// Integer set:
arr = [1,4,2,3,0,5];
// Target sum:
arg = 7;

// Generate hash table
hashTable = {};
arr.forEach(function(value, index){
hashTable[value] = index;
});

// hashTable = {
//   0: 4,
//   1: 0,
//   2: 2,
//   3: 3,
//   4: 1,
//   5: 5,
// }

for (var i = 0; i < arr.length; i++) {
if (hashTable[arg - arr[i]]) {
console.log([hashTable[arg - arr[i]], i])
}
}
``````

The solution should be 4,3 and 5,2 but i am getting 3,1 5,2 1,3 and 2,5. I can walk through the for loop with pen and paper and see that I am doing something wrong but I'm pretty sure I am following the langauge agnostic examples I found (for example here and here). Any help would be appreciated.

Answer Source

Here, you output indices of summands, while you need its values:

`````` console.log([hashTable[arg - arr[i]], i])
``````

That's why you get these values:

• 3, 1; which means item at index 3 + item at index 1 = 7
• 5, 2; which means item at index 5 + item at index 2 = 7 etc.

Try changing `i` in output to `arr[i]`, and `hashTable[arg - arr[i]]` to `arr[hashTable[arg - arr[i]]]`, it should work:

``````// Integer set:
var arr = [1,4,2,3,0,5];
// Target sum:
var arg = 7;

// Generate hash table
var hashTable = {};
arr.forEach(function(value, index){
hashTable[value] = index;
});

for (var i = 0; i < arr.length; i++) {
if (hashTable[arg - arr[i]]) {
console.log([arr[hashTable[arg - arr[i]]], arr[i]]);
}
}``````

Note that you get symmetric results too because 4 + 3 = 7 and 3 + 4 = 7 as well.
The solution can be optimized by checking while inserting:

``````var arr = [1, 4, 2, 3, 0, 5];
var arg = 7;

var hashtable = {};
arr.forEach(function(x) {
hashtable[x] = true;
if (hashtable[arg - x])
console.log([arg - x, x]);
})``````

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download