Solomon Bothwell - 8 months ago 48

Javascript Question

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

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]);
})
```

Source (Stackoverflow)