從總和等於給定數的未排序數組中查找給定數量的元素

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）