从总和等于给定数的未排序数组中查找给定数量的元素

Question

从总和等于给定数的未排序数组中查找给定数量的元素。

我写下面的代码，它几乎工作。但复杂度是O（n^2）。有更好的解决方案吗？

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

} 
})() 

Answer 1

您需要一个散列表来维护您访问的数字列表或给定数组中所有数字的列表。所以在每次迭代中，你会找到补数（给定总和数[i]）。由于您查找的不仅仅是一对值，因此您需要在散列表中查找加入这种补充的键。这里要说的是，hashmap的查找时间为O（1） - 假设没有/很少的冲突 - 而通过剩余数组的其余部分进行迭代将导致O（n^2）