唯一的求和对排列：Javascript算法

Question

我已经完成了一个低效但可行的算法，用于找到数组（arr1）中哪一对数字相加等于给定的和。我遇到了以下两个问题：

(1) 它会返回“每一对”数字（例如：当和为12时，既返回1+11，也返回11+1）；

(2) 我不想让它将一个数字与自身相加（例如：在findArrSum([1, 3, 4, 8, 9, 11, 6, ], 12)中，我不希望它返回（6+6）。我可以通过if语句忽略6，但这样会同时忽略解决方案（例如，在findArrSum([1, 3, 4, 8, 9, 11, 6, 6], 12)中的6+6）。

function findArrSum(arr1, sum) {   
  var i = 0;

  for (i in arr1) {
      arr1.map(function(num) {

       var answerSum = (num + arr1[i]);
       if (answerSum == sum && num != arr1[i]) {

                console.log(num +"+" +arr1[i] +"=" +sum);


                }
        });
    }
}
console.log('Enter an array and a sum that you want a pair to add to: ')

- Matty

---

一个简单的 fiddle http://jsfiddle.net 会有所帮助。 - gurvinder372

arr1.map(function(num, b) { 然后 num != arr1[i] 变成 (num != arr1[i] && i!=b) - dandavis

需要编辑吗？我有点困惑。 - Matty

为什么使用“for...in”进行数组迭代是一个坏主意？ - Oriol

那我会将它改为 for (i = 0; i < arr1.length-1; ++); 吗？ - Matty

Answer 1

您的两个问题都可以通过进行小的更改来解决，例如：

function findArrSum(arr1, sum) {   
  var i = 0;
  var usedSumArray = []; //new array introduced to store already done sums
  for (i in arr1) {
      arr1.map(function(num) {
       var thisSum = num +"+" +arr1[i]; //storing sum string
       if ( num != arr1[i] && usedSumArray.indexOf( thisSum ) == -1 ) //checking if the number is same or sum already done
       {
          usedSumArray.push( thisSum );
          var answerSum = (num + arr1[i]);
          if (answerSum == sum && num != arr1[i]) 
         {
            console.log(num +"+" +arr1[i] +"=" +sum);
         }
       }
     });
   }
}

- gurvinder372

Answer 2

一个朴素的算法是：

function findArrSum(arr, sum) {
  for(var i=0; i<arr.length; ++i)
    for(var j=i+1; j<arr.length; ++j)
      if(arr[i] + arr[j] === sum)
        console.log(arr[i] + ' + ' + arr[j] + ' = ' + sum);
}

但是这样的成本是n^2。我们可以通过先排序，然后使用二分搜索来做得更好。

function dicSearch(arr, item, from, to) {
  if(from === to) return -1;
  var mid = Math.floor((from + to) / 2);
  if(arr[mid] > item) return dicSearch(arr, item, from, mid);
  if(arr[mid] < item) return dicSearch(arr, item, mid+1, to);
  return mid;
}
function findArrSum(arr, sum) {
  arr.sort(function(a,b) {
    return a-b;
  });
  for(var i=0; i<arr.length; ++i) {
    var j = dicSearch(arr, sum-arr[i], i+1, arr.length);
    if(j >= 0)
      console.log(arr[i] + ' + ' + arr[j] + ' = ' + sum);
  }
}

这应该只需要花费n log n。当你找到最小值j时，甚至可以通过停止迭代来加快速度，而不是达到arr.length。

但是我们可以通过使用哈希表使其更快。

function findArrSum(arr, sum) {
  var hash = Object.create(null); // Also consider ES6 map
  for(var i=0; i<arr.length; ++i) {
    var j = hash[arr[i]];
    if(j != null)
      console.log(arr[i] + ' + ' + arr[j] + ' = ' + sum);
    hash[sum-arr[i]] = i;
  }
}

那只需要平均花费 n。

- Oriol

---

解决了问题和整体效率低下的情况。之前不知道在JavaScript中使用哈希表。 - Matty