JavaScript 程序：计算给定和的数对

---

给定一个包含 n 个整数的数组和一个给定的和 S，编写一个 JavaScript 程序来查找给定数组中元素对的总数，其和等于 S。计算给定和的数对是一个在求职面试中常见的题目，并且经常用于许多现实世界的应用中，例如密码学和数据压缩。

问题是找到数组中和等于给定值的数对的数量。在这篇博文中，我们将探讨解决此问题的不同方案及其时间和空间复杂度。

示例场景 1

Input 1: array[] = [2,4,3,1,2,5]
Input 2: S = 5 
Output: 3 

说明 − 在上面的数组中，我们有 3 对 (2,3)、(4,1) 和 (3,2) 的和为 5。

示例场景 2

Input 1: array[] = [2,4,3,1,2,5]
Input 2: S = 4 
Output: 2 

说明 − 在上面的数组中，我们有 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)); 

上面代码的输出如下所示 −

Original Array: 1,2,3,4,5
Number of pairs with sum 5: 2

时间复杂度：O(n^2)，因为我们在此方案中使用了嵌套循环。

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

使用哈希表计算给定和的数对

解决此问题的一个更有效的方案是使用哈希表存储数组中每个元素的频率，然后再次遍历数组以查找具有给定和的数对。

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

示例

此 JavaScript 程序使用哈希表来计算给定和的数对。

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 = [2, 3, 4, 5, 1];
console.log("Original Array: " + array)
let sum = 5; 
console.log("Number of pairs with sum 5: " + countPairsOptimized(array, sum));

上面代码生成以下输出 −

Original Array: 2,3,4,5,1
Number of pairs with sum 5: 2

时间复杂度：O(n)，因为我们只遍历数组一次。

空间复杂度：O(n)，因为我们使用了哈希映射。