A pair of elements from a given array, the sum of which is equal to a specific target number

Question

I am in the middle of my JavaScript session. Find this code in my coding exercise. I understand the logic, but I have not received this condition [nums [x]].

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 pairs of elements from a given array, the sum of which is equal to a specific target number. I wrote the code below.

 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 an optimized way than the above two solutions? Can someone explain the first solution what exactly displays [nums [x]] this condition points to?

Answer 1

the map value you see is a lookup table, and the twoSum method implemented what is called dynamic programming

In dynamic programming, you store the values ​​of your calculations, which you can use later to find a solution.

Let's see how it works in order to better understand this:

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

In iteration 0:

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

Thus, on our map 40 points to 0.

In iteration 2:

value 40. I look at the map my card to see that I previously found a pair for 40.

map[nums[x]] (the same as map[40] ) will return 0.
This means that I have a pair for 40 with index 0.
0 and 2 are a pair.

---

Does that make sense now?

Unlike your solution, where you have 2 nested loops, you can store previously calculated values. This will save you processing time, but consumes more memory space (because the lookup table will need memory)

Also, since you are writing this in javascript, your map may be an object, not an array. This will also make debugging a lot easier;)

Answer 2

Using the HashMap approach using time complexity approx O (n), the following code is shown below:

 let twoSum = (array, sum) => { let hashMap = {}, results = [] for (let i = 0; i < array.length; i++){ if (hashMap[array[i]]){ results.push([hashMap[array[i]], array[i]]) }else{ hashMap[sum - array[i]] = array[i]; } } return results; } console.log(twoSum([10,20,10,40,50,60,70,30],50)); 

result:

 {[10, 40],[20, 30]} 

I think the code itself explains, even if you want to help understand it, let me know. I will be quite pleased with my explanation.

Hope this helps.

Answer 3

Please try the code below. It will give you all unique pairs, the sum of which will be equal to targetSum. It performs a binary search, so it will be better in performance. The temporary complexity of this solution is O (NLogN)

 ((arr,targetSum) => { if ((arr && arr.length === 0) || targetSum === undefined) { return false; } else { for (let x = 0; x <=arr.length -1; x++) { let partnerInPair = targetSum - arr[x]; let start = x+1; let end = (arr.length) - 2; while(start <= end) { let mid = parseInt(((start + end)/2)); if (arr[mid] === partnerInPair) { console.log(`Pairs are ${arr[x]} and ${arr[mid]} `); break; } else if(partnerInPair < arr[mid]) { end = mid - 1; } else if(partnerInPair > arr[mid]) { start = mid + 1; } } }; }; })([0,1,2,3,4,5,6,7,8,9], 10) 

Answer 4

 function twoSum(arr, S) { const sum = []; for(let i = 0; i< arr.length; i++) { for(let j = i+1; j < arr.length; j++) { if(S == arr[i] + arr[j]) sum.push([arr[i],arr[j]]) } } return sum } 

Brute force is not the best way to decide, but it works.

Answer 5

 function twoSum(arr, target) { let res = []; let indexes = []; for (let i = 0; i < arr.length - 1; i++) { for (let j = i + 1; j < arr.length; j++) { if (target === arr[i] + arr[j] && !indexes.includes(i) && !indexes.includes(j)) { res.push([arr[i], arr[j]]); indexes.push(i); indexes.push(j); } } } return res; } console.log('Result - ', twoSum([1,2,3,4,5,6,6,6,6,6,6,6,6,6,7,8,9,10], 12) ); 

Brute force.