Monday, May 20, 2024
 Popular · Latest · Hot · Upcoming
84
rated 0 times [  90] [ 6]  / answers: 1 / hits: 39262  / 8 Years ago, sun, may 1, 2016, 12:00:00

I am in mid of my JavaScript session. Find this code in my coding exercise. I understand the logic but I didn't get this map[nums[x]] condition.



function twoSum(nums, target_num) {  
var map = [];
var indexnum = [];

for (var x = 0; x < nums.length; x++)
{
if (map[nums[x]] != null)
// what they meant by map[nums[x]]
{
index = map[nums[x]];
indexnum[0] = index+1;
indexnum[1] = x+1;
break;
}
else
{
map[target_num - nums[x]] = x;
}
}
return indexnum;
}
console.log(twoSum([10,20,10,40,50,60,70],50));


I am trying to get the Pair of elements from a specified array whose sum equals a specific target number. I have written below code.



function arraypair(array,sum){
for (i = 0;i < array.length;i++) {
var first = array[i];
for (j = i + 1;j < array.length;j++) {
var second = array[j];

if ((first + second) == sum) {
alert('First: ' + first + ' Second ' + second + ' SUM ' + sum);
console.log('First: ' + first + ' Second ' + second);
}
}

}
}

var a = [2, 4, 3, 5, 6, -2, 4, 7, 8, 9];

arraypair(a,7);


Is there any optimized way than above two solutions? Can some one explain the first solution what exactly map[nums[x]] this condition points to?


More From » arrays

 Answers
70

that map value you're seeing is a lookup table and that twoSum method has implemented what's called Dynamic Programming



In Dynamic Programming, you store values of your computations which you can re-use later on to find the solution.



Lets investigate how it works to better understand it:



twoSum([10,20,40,50,60,70], 50)
//I removed one of the duplicate 10s to make the example simpler


In iteration 0:



value is 10. Our target number is 50. When I see the number 10 in index 0, I make a note that if I ever find a 40 (50 - 10 = 40) in this list, then I can find its pair in index 0.



So in our map, 40 points to 0.



In iteration 2:



value is 40. I look at map my map to see I previously found a pair for 40.



map[nums[x]] (which is the same as map[40]) will return 0.

That means I have a pair for 40 at index 0.

0 and 2 make a pair.






Does that make any sense now?



Unlike in your solution where you have 2 nested loops, you can store previously computed values. This will save you processing time, but waste more space in the memory (because the lookup table will be needing the memory)



Also since you're writing this in javascript, your map can be an object instead of an array. It'll also make debugging a lot easier ;)


[#62338] Thursday, April 28, 2016, 8 Years  [reply] [flag answer]
Only authorized users can answer the question. Please sign in first, or register a free account.
chazw

Total Points: 127
Total Questions: 129
Total Answers: 92

Location: Sao Tome and Principe
Member since Wed, Dec 21, 2022
1 Year ago
;