計算公平對的數量

2563。計算公平對的數量

難度：中

主題：陣列、兩個指標、二分查找、排序

給定一個 0 索引的 大小為 n 的整數數組 nums 和兩個上下整數，傳回 公平對的數量 .

一對 (i, j) 是 公平如果：

• 0
• 下

範例1：

• 輸入： nums = [0,1,7,4,4,5]，下= 3，上= 6
• 輸出： 6
• 解釋： 有6 個公平對：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和(1,5) .

範例2：

• 輸入： nums = [1,7,9,2,5]，下= 11，上= 11
• 輸出： 1
• 解釋： 有一個公平對：(2,3)。

約束：

• 1 5
• nums.length == n
• -10⁹ 9
• -10⁹ 9

提示：

1. 依升序對陣列進行排序。
2. 對於數組中的每個數字，追蹤數組中可以與該數字形成公平對的最小和最大數字。
3. 當您移動到更大的數字時，兩個邊界都會向下移動。

解：

我們可以使用以下方法：

1. 對陣列進行排序：排序幫助我們利用雙指標技術並更有效地執行二分搜尋。
2. 雙指標技術：對於排序數組中的每個元素，我們可以計算可以與其形成公平對的元素的範圍。我們使用二分搜尋來找到這個範圍。
3. 邊界二分搜尋：對於每個元素 nums[i]，找出範圍 [lower, upper] - nums[i]，其中 j > ；我。我們使用二分搜尋來尋找滿足此範圍的最小和最大索引。

讓我們用 PHP 實作這個解：2563。計算公平對的數量

解釋：

1. 排序：我們將陣列 nums 進行排序，以便更容易透過二分搜尋找到有效的對。
2. 二分搜尋範圍：
   • 對於每個元素 nums[i]，我們找到低值和高值，這是我們希望總和落入的範圍。
   • 我們使用兩次二分搜尋來找出索引範圍 [left, right)，其中 nums[i] nums[j] 落在 [lower, upper] 內。
3. 計數對：我們為每個 i 增加左右之間有效索引的計數。

由於對每個元素進行排序和二分搜索，這種方法的時間複雜度為 O(n log n)，這對於大型輸入來說足夠高效。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是計算公平對的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！