javascript - 在 "kn"而不是 "n^2"时间求解数组值的和练习

Question

我有以下功能:

function myFunction(array, sum){
     for(var i = 0; i < array.length; i++){
          var firstValue = array[i];
              for(var x = i + 1; x < array.length; x++){
                    var secondValue = array[x];
                    if((firstValue + secondValue) == sum){
                        return i + ": " + x; 
                    }
              }
     }
     return "No two array values match the sum";
}

上面有两个参数；第一个数组，第二个和。它找到数组中的前两个数字，当它们与第二个参数相加时。然后返回与第二个参数相加的两个数字的数组索引。现在，上面的函数在n^2 时间内解决了这个问题。有没有办法在 kn 时间内解决同样的问题？

我用 JavaScript 编写了函数，但这适用于所有现代语言。

Answer 1

这是一个二和问题。对于这个问题，一般有 2 种有效的算法。

1)哈希法，你为每一个值创建一个哈希表，对于每一个值v，查找sum-v即可。

function myFunction(array, sum){
 hash h;
 for(var i = 0; i < array.length; i++){
      if (h.find(sum-array[i])) return "found";
      h.insert(array[i]);
 }
 return "No two array values match the sum";

时间和空间复杂度都是O(N)。

2) 另一种方法是先对数组进行排序，然后使用 2 索引查找。

function myFunction(array, sum){
     sort(arrary);
     var i = 0, j = array.length-1;
     while (i < j) {
       if (array[i] + array[j] == sum) return "Found";
       else if (array[i] + array[j] > sum) --j;
       else ++i;
     }
     return "No two array values match the sum";
   }

它花费了 O(NlnN) 时间和 O(1) 空间。

要返回值的 2-index，您应该将索引存储在哈希表和您排序的数组中。