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 – element）是否在哈希表中。如果补充存在，我们将计数器增加补充的频率。

例如–

让我们取数组[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.

同样地，对于其他指标

对于index=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)，因为我们使用了哈希映射。