用给定总和对进行计数的 Javascript 程序
用给定总和对进行计数是计算机科学中常见的问题，并且经常用于许多实际应用中，例如密码学和数据压缩。问题是找出数组中总和等于给定值的对的数量。在这篇博文中，我们将探讨这个问题的不同解决方案及其时间和空间复杂度。
给定一个包含 n 个整数的数组和一个给定的和 S，找出给定数组中和等于 S 的元素对的总数。
输入
array[]=[2,4,3,1,2,5], S=5
输出
3
解释 − 在上面的数组中，我们有 3 对 (2,3)、(4,1) 和 (3,2)，和为 5。
输入
array[]=[2,4,3,1,2,5], S=4
输出
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));
由于我们在此解决方案中使用了嵌套循环，因此上述解决方案的时间复杂度为 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.
对于其他索引，同样如此
对于 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("和为 5 的对数: " + countPairsOptimized(array, sum));
此解决方案的时间复杂度为 O(n)，因为我们只遍历数组一次。空间复杂度为 O(n)，因为我们使用哈希映射；
结论
在本教程中，我们探索了对给定总和的对数计数问题的不同解决方案。蛮力解决方案的时间复杂度为 O(n^2)，空间复杂度为 O(1)，而优化解决方案的时间复杂度为 O(n)，空间复杂度为 O(n)。我们希望本博客能帮助您更好地理解这个概念。
