題目資訊

題目編號: 2563
題目連結: Count the Number of Fair Pairs
主題: Array, Two Pointers, Binary Search, Sorting

題目敘述

給定一個0-索引的整數陣列 nums，大小為 $n$，以及兩個整數 lower 和 upper，返回公平數對的數量。

當數對 (i, j) 公平時：

$0 \leq i < j < n$，且
$lower \leq nums[i] + nums[j] \leq upper$

範例 1:

輸入: nums = [0,1,7,4,4,5], lower = 3, upper = 6
輸出: 6
解釋: 有 6 個公平數對: (0,3), (0,4), (0,5), (1,3), (1,4), 和 (1,5)。

範例 2:

輸入: nums = [1,7,9,2,5], lower = 11, upper = 11
輸出: 1
解釋: 只有一個公平數對: (2,3)。

約束條件:

$1 \leq nums.length \leq 10^5$
$nums.length == n$
$-10^9 \leq nums[i] \leq 10^9$
$-10^9 \leq lower \leq upper \leq 10^9$

直覺

這個問題要求我們找出數組中滿足特定條件的索引對，其條件與它們的和有關。一種直接的方法是使用嵌套迴圈計算所有可能的索引對並檢查其和是否落在指定的範圍內。然而，這種簡單的方法對於大型數組來說效率不高，因為其時間複雜度為 $\mathcal{O}(n^2)$。因此，一種更有效的方法是先對數組進行排序，並利用二分搜尋來顯著減少計數公平對所需的比較次數。

解法

此解法利用排序後的數組來有效地計算其和落在給定範圍內的索引對。具體步驟如下：

初始化：建立一個空列表 previousNumbers，用來按順序記錄迄今為止處理過的數字；以及一個計數器 fairPairCount，初始值為零，用來記錄符合條件的索引對數量。
遍歷數組：對於每個數組 nums 中的元素 num：
- 範圍二分搜尋：使用二分搜尋來確定 previousNumbers 中可與 num 形成公平對的有效範圍。具體來說，採用：
  - lower_bound 來找到 previousNumbers 中第一個加上 num 後不小於 lower 的元素。
  - upper_bound 來找到 previousNumbers 中第一個加上 num 後大於 upper 的元素。
- 計算有效索引數量：使用 upper_bound 和 lower_bound 迭代器之差來獲取滿足條件的有效索引數量。
插入並維持順序：將當前元素 num 插入到 previousNumbers 中，以維持此列表的排序順序。這一步確保 previousNumbers 準備好進入下一次迭代。
返回計數：在處理完所有元素後，fairPairCount 將包含所有滿足條件的索引對的總數。

透過維持一個已排序的數字列表並使用二分搜尋來有效尋找範圍，此解法將計數公平對的問題簡化為可在 $\mathcal{O}(n \log n)$ 時間複雜度內解決。這一顯著的提升是通過排序、二分搜尋和巧妙地使用資料結構共同實現的，為問題提供了一個具規模性的解法。

程式碼

C++

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        vector<int> previousNumbers;
        long long fairPairCount = 0;

        for (int num : nums) {
            // 尋找下界：第一個不小於(lower - num)的元素
            vector<int>::iterator lowerBoundIt = lower_bound(previousNumbers.begin(), previousNumbers.end(), lower - num);

            // 尋找上界：第一個大於(upper - num)的元素
            vector<int>::iterator upperBoundIt = upper_bound(previousNumbers.begin(), previousNumbers.end(), upper - num);

            // 計算範圍在[lower - num, upper - num]內的元素數量
            fairPairCount += upperBoundIt - lowerBoundIt;

            // 將'num'插入到'previousNumbers'中的排序位置
            previousNumbers.insert(upper_bound(previousNumbers.begin(), previousNumbers.end(), num), num);
        }

        return fairPairCount;
    }
};

Python

class Solution:
    def countFairPairs(self, nums, lower, upper):
        previousNumbers = []
        fairPairCount = 0

        for num in nums:
            # 尋找下界：第一個不小於 (lower - num) 的元素
            lowerBoundIt = self.lower_bound(previousNumbers, lower - num)

            # 尋找上界：第一個大於 (upper - num) 的元素
            upperBoundIt = self.upper_bound(previousNumbers, upper - num)

            # 計算範圍內 [lower - num, upper - num] 的元素個數
            fairPairCount += upperBoundIt - lowerBoundIt

            # 將 'num' 插入到 'previousNumbers' 中的排序位置
            previousNumbers.insert(self.upper_bound(previousNumbers, num), num)

        return fairPairCount

    def lower_bound(self, nums, target):
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

    def upper_bound(self, nums, target):
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid
        return left

複雜度分析

時間複雜度: 時間複雜度是 $O(n \log n)$。這是因為對於輸入向量 nums 中的每一個元素，我們在向量 previousNumbers 上執行 lower_bound 和 upper_bound 操作，這兩者在最壞情況下都需要 $O(\log n)$ 的時間，因為向量是維持在排序狀態下。此外，使用 upper_bound 將元素插入排序向量 previousNumbers 也需耗費 $O(\log n)$ 的時間。由於 nums 中有 $n$ 個元素，因此總體時間複雜度是 $O(n \log n)$。
空間複雜度: 空間複雜度是 $O(n)$。這是因為我們使用輔助向量 previousNumbers 來存儲到目前為止已經看過的數字，這些數字是按排序順序存放的，在最壞情況下可以包含來自輸入向量 nums 的所有 $n$ 個元素。因此，空間複雜度是 $O(n)$。

CS Note
En

Leetcode 2563. Count the Number of Fair Pairs

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析