refactorized solve for an algorithm in javascript
I have attended a technical interview for a development company. They asked me the following:
Giving an array of numbers (n) find 2 numbers that sum gives (k) and print them.
e.g
Input: n = [2,6,4,5,7,1], k = 8
Output: result=(2,6),(7,1)
My solution:
function findSum(n,k){
let aux = []
for (let i = 0; i < n.length; i++) {
for (let j = i+1; j < n.length; j++) {
if (n[i] + n[j] == k) {
aux.push({ first: n[i], second: n[j] })
}
}
}
return aux;
}
They told me that, it is possible to make the exercise with some kind of key or mapping.
Does some one know how to do it with only one loop?
7 answers

A task like this can be as simple or as complicated as you want to make it. Here's one solution, for example:
function findPairs(n, k) { return n.reduce((pairs, next, i) => pairs.concat( n.slice(i + 1) .filter(num => next + num === k) .map(num => [ next, num ]) ), [] ); }
For the inputs
[2, 6, 4, 5, 7, 1]
and8
will output[ [2, 6], [7, 1] ]
. 
 Sort the array in nondecreasing order.
 Initialize two index variables to find the candidate elements in the sorted array. Initialize
l
to the leftmost index:l = 0
, Initializer
to the rightmost index:r = n.length  1
 Loop while
l
<r
.if (n[l] + n[r] == k)
thenreturn 1
else if( n[l] + n[r] < k )
thenl++
else r
 No candidates in whole array 
return 0

Match a number
x
from array with a keyMath.min(x, k  x)
. Then run through your array and store every number in a hash using mentioned key. When the key you are going to add already is in the hash  check if stored value and current number gives required sum.function findSum(n, k){ let hash = {}; for(let i = 0; i < n.length; ++i){ let x = n[i], key = Math.min(x, k  x); if((key in hash) && hash[key] + x == k) return [hash[key], x]; else hash[key] = x; } }

I think by sorting you can do that
var n = [2,6,4,5,7,1]; var k = 8 ; n.sort(); let start = 0, end = n.length1; while(start < n.length && end >= 0) { let current_sum = (n[start] + n[end]); if(current_sum == k) { console.log('Found sum with '+ n[start] +' and '+ n[end]); break; } else if(current_sum > k) { end; } else { start++; } } if(start == n.length  end < 0) { console.log('Not Found'); }
but while writing this code I got one another approach also
const set = new Set([2,6,4,5,7,1]); var k = 8; let found = false; for (let item of set) { let another = k  item; if(set.has(another)){ console.log('found with '+item +' and ' +another); found = true; break; } } if(!found) { console.log('Not found'); }

If numbers are nonnegative and the target value is within JavaScript array limit:
function findsums(arr,k){ var ret=[]; var aux=[]; arr.forEach(function(i){ if(i<=k){ if(aux[ki]) ret.push([ki,i]); aux[i]=true; } }); return ret; } console.log(findsums([2,6,4,5,7,1],8));
Similar approach could work with a bitfield (or even with a sparse array of bitfields) too.

The key to solving a question like this with low time complexity is the ability to efficiently search the data structure. A lot of answers rearrange the array in a way where searching an array is optimized. Another approach is with a data structure that inherently has fast search.
Set and Map data structures have O(1) time complexity for searches, which make them good data structures where searching can be leveraged to increase performance.
I use a
new Map
and traverse the array while adding it as a key. I set thekey
to the number and the value to the number of times I see it. I use a map over anew Set
because I can also keep track of the number of instances of that particular number.I search for the number that would sum up to
k
, which is: (k
num
). If I find that number, I add both numbers to my results data structure and decrement thevalue
by 1, to show that it's been used.Time complexity: O(n), memory complexity: O(2n). Twice the amount of space compared to the original array because I have a
key
and avalue
to store in myMap
function pairSums(arr, k){ const map = new Map const matches = [] for (let num of arr) { const search = k  num if (map.get(search) > 0) { matches.push([num, k  num]) map.set(search, map.get(search)  1) } else if (!map.has(num)){ map.set(num, 1) } else { map.set(num, map.get(num) + 1) } } return matches } console.log(pairSums([2, 6, 6, 6, 2, 4, 4, 4, 5, 7, 1, 4, 2], 8))

Minified alternative similar to @Andrew's great answer, but assumes that all numbers are above 0 :
var pairs = (arr, k) => arr.reduce((a, n) => (a[n  k] ? a.push([n, k  n]) : a[n] = a[n]  0 + 1, a), []); console.log(JSON.stringify( pairs([2,6,4,5,7,1], 8) ));