1

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.

Improve this question
4
  • There's a very concise solution to this problem that would be relatively easy to translate into JavaScript. Commented Nov 18, 2016 at 4:06
  • 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. Commented Nov 18, 2016 at 4:10
  • @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. Commented Nov 18, 2016 at 4:23
  • Dynamical programming bottom to up approach should be the best Commented Nov 18, 2016 at 9:35

5 Answers 5

Reset to default
1

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

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

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).
@SolomonBothwell Oh, yes, you need to wrap the first summand with arr[] too, since you need its value too. See my updated answer.
Oh I see! Thanks so much. Your shortened answer looks really cool too. Im studying it right now.
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.
Actually scratch my last comment. That fix only works if there are no duplicate values in the array. Try running it with arr = [1, 1, 1] and arg = 2
1 
function solution(arr, n){
var map = {};
for (var i = 0; i < arr.length; i++) {
    if (map[arr[i]] !== undefined) {
        console.log(arr[i], n - arr[i]);
    }
    map[n - arr[i]] = i;
  }
 }
Improve this answer

Comments

0

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

Improve this answer

Comments

0

Below Function working fine for multiple cases.

   const twoSum = (numArr, target) => { 
        let numObject = {};
        numArr.forEach((value, index) => numObject[value] = index);
        for (let i = 0; i < numArr.length; i++) {
            let diff = target - numArr[i];
            if (numObject.hasOwnProperty(diff) && numObject[diff] !== i) {
                return [i, numObject[diff]];
            }
        }
    }
Improve this answer

Comments

0 

const arr = [1, 2, 3, 4,5,6];
let target = 9;
let indexs = [];
function sumNew(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i+1; j < arr.length; j++) {
            if ( arr[i] + arr[j]==target) {
               indexs.push(i,j);
               return indexs;
            }

        }
    }
}
let result = sumNew(arr,target);
console.log(result);

Improve this answer

1 Comment

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.