Javascript程序计算具有给定和的配对

计算具有给定和的数对是计算机科学中的一个常见问题，并且经常被用于许多现实世界中的应用，如密码学和数据压缩。这个问题是要找到一个数组中总和等于给定值的对的数量。在这篇博文中，我们将探讨这个问题的不同解决方案及其时间和空间的复杂性。

给定一个由n个整数组成的数组和一个给定的总和S，找出给定数组中总和等于S的元素对的总数。

输入

array[]=[2,4,3,1,2,5], S=5

输出

解释 - 在上述数组中，我们有3对(2,3)，(4,1)和(3,2)，总和为5。

输入

array[]=[2,4,3,1,2,5], S=4

输出

解释 - 在上述数组中，我们有2对(2,2),(3,1)，总和等于4。

蛮力解决

这个问题最简单的解决方法是遍历输入数组中所有的元素对，检查它们的和是否等于给定的和。对于每一对元素，我们检查它们的总和是否等于S，如果是，我们增加一个计数器。这里我们将使用嵌套循环来达到这个目的。

例子

function countPairsBruteForce(arr, S) {
   let counter = 0;
   for (let i = 0; i < arr.length; i++) {
      for (let j = i + 1; j < arr.length; j++) {
         if (arr[i] + arr[j] === S) {
            counter++;
         }
      }
   }
   return counter;
}
let arr= [ 1,2,3,4,5];
console.log("Original Array: " + arr) 
let sum = 5;
console.log("Number of pairs with sum 5: "+ countPairsBruteForce(arr, sum));

上述解决方案的时间复杂度为O(n^2)，因为我们在这个解决方案中使用了嵌套循环。

空间复杂度为O(1)，因为我们没有使用任何额外的空间。

优化的解决方案

一个更有效的解决方案是使用一个哈希表来存储数组中每个元素的频率，然后再次迭代数组来寻找具有给定和的配对。

对于数组中的每个元素，我们检查该元素的补码（S-元素）是否在哈希表中。如果补码存在，我们用补码的频率来增加计数器。.

比如说

让我们把数组[1,2,3,4,5]的答案S=5

在哈希表中插入数组的每个元素及其频率

hash_table[1]=1
hash_table[2]=1
hash_table[3]=1
hash_table[4]=1
hash_table[5]=1

初始化一个变量来存储配对的数量，让它成为count。

For index=0,
if(hash[sum-arr[0]] is present in the hash map, i.e.
if(hash[5-1] is present , increment the counter by the frequency of the element.

同样地，对于其他指数

对于指数=1

hash[5-arr[1]] =hash[5-2] = hash[3] is present in array
So, counter+=1;

For index=2
hash[5-arr[2]] =hash[5-3] = hash[2] is present in array
So, counter+=1;

For index=3
hash[5-arr[3] =hash[5-4] = hash[1] is present in array
So, counter+=1;

For index=4
hash[5-arr[4]] =hash[5-5] = hash[0] is not present in array
Therefore, don't increment the counter.

现在我们得到的数字是实际答案的两倍，因为我们对每一对进行了两次计数，因此将计数变量除以2。

例子

function countPairsOptimized(arr, S) {
   let count = 0;
   let hash_map = {};
   for (let ind = 0; ind < arr.length; ind++) {
      if (!hash_map[arr[ind]]) {
         hash_map[arr[ind]] = 0;
      }
      hash_map[arr[ind]]++;
   }
   for (let i = 0; i < arr.length; i++) {
      if (hash_map[S - arr[i]]) {
         count += hash_map[S - arr[i]];
      }
   }
   return count/2;
}
let array = [ 1,2,3,4,5];
console.log("Original Array: " + array)
let sum = 5; 
console.log("Number of pairs with sum 5: " + countPairsOptimized(array, sum));

这个解决方案的时间复杂度为O(n)，因为我们只对数组进行一次遍历。空间复杂度是O(n)，因为我们使用的是哈希图。