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)，因為我們使用了雜湊對映。