首頁  >  文章  >  web前端  >  JavaScript 程式計算總和小於給定值的三元組

JavaScript 程式計算總和小於給定值的三元組

PHPz
PHPz轉載
2023-09-24 22:37:021503瀏覽

JavaScript 程序计算总和小于给定值的三元组

我們將寫一個 JavaScript 程式來計算總和小於給定值的三元組的數量。這個問題可以透過對陣列進行排序並使用兩個指標來檢查可能的組合來解決。首先,我們按升序對陣列進行排序,然後,對於陣列中的每個元素,我們將使用兩個指標來檢查總和小於給定值的三元組。這樣的三元組的數量將是我們將追蹤的計數。

此外,我們將根據三元組總和小於或等於給定值來更新計數和指標。這樣,我們就能以 O(n^2) 的時間複雜度有效率地解決問題。這是一種非常有用的技術,需要記住,以應對未來的問題,我們需要找到滿足特定條件的某些組合的計數。

最後,我們將傳回總和小於給定值的此類三元組的計數。

方法

  • 首先,按升序對給定的數字數組進行排序。

  • 初始化三個變數:left、right 和 count。

  • 然後使用兩個指標的方法,左指標從0開始,右邊指標從end開始。

  • 對於每次迭代,計算目前三元組的總和(左指向的元素 右指向的元素 目前元素)。

  • 如果總和小於給定值,則增加計數和左指標。

  • 如果總和大於給定值,則遞減右邊指標。重複此過程,直到左指針小於右指針。

範例

這是一個 JavaScript 程式的完整範例,用於計算總和小於給定值的三元組的數量 -

function countTriplets(arr, sum) {
   let count = 0;
   arr.sort((a, b) => a - b); 
   // sorting the array in ascending order
   for (let i = 0; i < arr.length - 2; i++) {
      let left = i + 1;
      let right = arr.length - 1;
      while (left < right) {
         if (arr[i] + arr[left] + arr[right] >= sum) {
         right--;
         } else {
            count += right - left;
            left++;
         }
      }
   }
   return count;
}
const arr = [5, 1, 3, 4, 7];
const sum = 12;
console.log(countTriplets(arr, sum));

說明

  • countTriplets 函數採用陣列 arr 和值 sum 作為其參數。

  • count 變數用於追蹤總和小於 sum 的三元組的數量。

  • #arr 使用排序函數依升序排序。

  • 外部循環for (let i = 0; i 迭代數組,left和right 指針分別初始化為i 的下一個索引和陣列的最後一個索引。

  • while (left 迴圈繼續進行,直到 left 指標大於或等於 right 指標。

  • while (left 迴圈一直持續,直到左邊指標大於或等於右指標。

  • while迴圈的每次迭代中,arr[i]、arr[left]、arr[right] 已計算。如果該總和大於或等於總和,則指標遞減。如果總和小於總和,則計數將增加之間剩餘元素的數量b> 指針,left 指標遞增。

  • 函數傳回count變量,它表示總和小於sum的三元組的數量。

#

以上是JavaScript 程式計算總和小於給定值的三元組的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除