current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
up vote 0 down vote favorite

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.

share|improve this question
    
There's a very concise solution to this problem that would be relatively easy to translate into JavaScript. – Anderson Green 1 hour ago
    
On the second pass of your loop 7-4 is 3. Are you operating on a separate math plane than the rest of the planet? hashTable[3] would still be 3. – PHPglue 59 mins ago
    
@PHPglue sorry I'm really not sure what you are getting at. its an unsorted list and the value 3 happens to be at index 3. – Solomon Bothwell 47 mins ago
up vote 0 down vote accepted

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

share|improve this answer
    
hmm. yes i see that makes sense. your change fixed it when i = 1 but when i = 3 the output is [1,3] (because the key 4 in hashTable has value 1). – Solomon Bothwell 51 mins ago
    
@SolomonBothwell Oh, yes, you need to wrap the first summand with arr[] too, since you need its value too. See my updated answer. – Yeldar Kurmangaliyev 47 mins ago
    
Oh I see! Thanks so much. Your shortened answer looks really cool too. Im studying it right now. – Solomon Bothwell 42 mins ago
1  
I noticed a bug in both versions. Change the target value to 4 and it will sum the same element (2 in this case). Adding [arg - x] != x to the if statement solves this. – Solomon Bothwell 23 mins ago
up vote 0 down vote

Try this out:

function sumPairs(inputArray, expectedSum){
  var a = inputArray.slice(), b = inputArray.slice(), l = a.length, p = [];
  for(var i=0,av; i<l; i++){
    av = a[i];
    for(var n=1,bv; n<l; n++){
      bv = b[n];
      if(av + bv === expectedSum){
        p.push([av, bv]);
      }
    }
  }
  return p;
}
console.log(sumPairs([1,4,2,3,0,5], 7));

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.