求和对的独特排列:Javascript算法

Unique Permutations of Summing Pairs: Javascript Algorithm

本文关键字：Javascript 算法 排列 求和      更新时间：2023-09-26

我已经完成了一个效率低下但有效的算法，用于计算数组中的哪对数字(arr1)加起来的总和。我面临这两个问题：

（

1）它给了我"每个"对（例如，当总和为12时，1+11和11+1），

和

（

2）我不希望它给自己添加一个数字（例如 findArrSum([1, 3, 4, 8, 9, 11, 6, ], 12) 我不希望它返回 （6+6））。我可以通过我的 if 语句使它忽略 6，但在这种情况下，它也会忽略解决方案（此示例中的 6+6 findArrSum([1, 3, 4, 8, 9, 11, 6, 6], 12) .

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: ')

一个朴素的算法将是

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。

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

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);
         }
       }
     });
   }
}
相关文章：