Find given numbers of elements from an unsorted array whose sum equals a given number

Question

Find given numbers of elements from an unsorted array whose sum equals a given number.

I have write the below code, it's almost work. but the complexity is O(n^2). Is there a better solution?

(function test(sum = 14, n = 4, nums = [7, 6, 1, 3, 2, 5, 4]) {

  for (var i = 0; i < nums.length; i++) {
    var rest = sum
    var ret = []
    var j = i;
    do {
      if (rest - nums[j] >= 0) {
      rest = rest - nums[j]
    } else {
      j++
      continue
    }

    ret.push(nums[j])

    if (rest == 0 && ret.length == n) {
      console.log("done", ret)
    }
    j++
 } while (j < nums.length)

}
})()

Do you have a question, or do you just want someone to do your homework? — JJJ, Apr 11 '17 at 07:04
@TimBiegeleisen I found some solution those just resolve find a pair of numbers equals given sum. — Anders Lau, Apr 11 '17 at 07:10
You should at least include your code and actual question. As it stands now, your question looks like a homework dump showing zero effort. — Tim Biegeleisen, Apr 11 '17 at 07:11
@TimBiegeleisen I have updated problem. I'm not do homework. — Anders Lau, Apr 11 '17 at 09:23
Possible duplicate of [Find a pair of elements from an array whose sum equals a given number](http://stackoverflow.com/questions/4720271/find-a-pair-of-elements-from-an-array-whose-sum-equals-a-given-number) — Paul Hankin, Apr 11 '17 at 11:03
@PaulHankin thanks . I need to specific number of elements . that just find a pair of elements. — Anders Lau, Apr 11 '17 at 13:00

score 2 · Accepted Answer · answered Apr 11 '17 at 14:46

You would need a hashtable to maintain a list of numbers you visited or list of all numbers in the given array. So at each iteration, you find the complement (given sum - nums[i]). Since you looking for more than a pair of values, you would need to find keys in the hashtable that add up to such complement. The takeaway here is that hashmap has lookup time of O(1)--assuming no/few collisions--whereas iterating through rest of remaining array would result in O(n^2)

Find given numbers of elements from an unsorted array whose sum equals a given number

1 Answers1