JavaScript 中陣列中是否存在和為特定值的數對

在本文中，我們將瞭解如何在陣列中找到一對元素，其和等於特定目標數字。因此，我們將使用 JavaScript 來實現該演算法。

理解問題

眼前的問題是在陣列中找到一對數字，其和等於給定的目標值。並且目標值也應該存在於陣列中。或者我們可以說，我們必須識別 (a, b) 對，其中 a + b = c，並且 c 也存在於陣列中。

給定問題的邏輯

為了解決這個問題，我們將使用雜湊集來儲存陣列的元素。因此，我們需要遍歷陣列中的元素，並檢查條件，即當前元素與任何其他元素的差是否出現在雜湊集中。如果條件滿足，則我們找到了和出現在陣列中的數對。

演算法

步驟 1：由於我們必須找出和等於給定目標值的元素對，並且目標值也應該存在於陣列中。因此，為了執行此任務，我們將建立一個函式。在這個函式中，我們將傳遞陣列作為引數 arr。

步驟 2：建立函式後，我們需要初始化一個空的雜湊集來儲存結果元素對陣列。

步驟 3：現在我們有一個函式和一個變數來儲存結果。在此之後，我們將使用迴圈迭代給定陣列中的每個元素。

步驟 4：在這個迴圈中，我們將檢查條件，如果 num 與任何其他元素的差存在於雜湊集中。因此，如果差存在於集合中，則將該對新增到結果變數中。

步驟 5：執行上述步驟後，我們將 num 新增到雜湊集中並返回結果。結果將包含和出現在給定陣列中的元素對。

示例

// Function for finding pairs with the sum
function findPairsWithSumExists(arr) {
   const hashSet = new Set();
   const result = [];

   for (let i = 0; i < arr.length; i++) {
      const num = arr[i];

      for (let j = 0; j < arr.length; j++) {
         if (j === i) continue; // Skip the same element

         const diff = num - arr[j];
         if (hashSet.has(diff)) {
            result.push([num, arr[j]]);
         }
      }

      hashSet.add(num);
   }

   return result;
}

const arr = [1, 2, 3, 4, 5];
const pairs = findPairsWithSumExists(arr);
console.log(pairs);

輸出

[
   [ 2, 1 ], [ 3, 1 ],
   [ 3, 2 ], [ 4, 1 ],
   [ 4, 2 ], [ 4, 3 ],
   [ 5, 1 ], [ 5, 2 ],
   [ 5, 3 ], [ 5, 4 ]
]

複雜度

查詢和等於給定目標值的數字對的時間複雜度為 O(n^2)，其中 n 是給定陣列的大小。造成這種複雜度的原因為我們使用了巢狀迴圈來迭代陣列。並且程式碼的空間複雜度為 O(n)，因為我們使用了雜湊集來儲存結果。

結論

正如我們已經生成了根據給定問題查詢元素對的程式碼。透過使用雜湊集儲存陣列的元素，我們可以有效地找到和出現在陣列中的數字對。並且該演算法具有二次時間複雜度和線性空間複雜度。

更新於： 2023-08-16

202 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告