Leetcode-2563. 统计公平数对的数目

思路

二分查找

解题过程

首先需要理解：顺序并不影响公平数对的个数。因为满足公平数对条件必然存在先后关系，排序后也并不改变这一点。所以可以先对数组进行排序。排序后才便于用二分查找寻找边界。

其次不能二重循环遍历，会超过时间限制，可以选择固定公平数对的一个数，查找符合条件的另一个数。为了避免重复计算，在考虑num[i]的另一个数的时候，只考虑nums[0~i-1]是否符合条件。

当固定了nums[i]的时候，只要另一个数的大小满足条件lower-nums[i]≤nums[0~i-1]≤upper-nums[i]即可。

根据上述思路，就考虑到用二分查找来寻找边界。也就是i左侧第一个大于等于lower-nums[i]的位置和i左侧最后一个小于等于upper-nums[i]的位置。其中的数都满足条件，就可以更新结果计数。

二分查找模板

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

code

c++

手写二分

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        long long ans = 0;
        int n = nums.size();
        sort(nums.begin(), nums.end());

        // 维护(x,i)对
        for (int i = 1; i < n; i++) {
            int low_req = lower - nums[i];
            int up_req = upper - nums[i];

            // 二分查找 i 左侧第一个大于等于low_req的位置
            int l = 0, r = i - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (nums[mid] >= low_req) r = mid;
                else l = mid + 1;
            }
            int low_idx = l;

            // 二分查找 i 左侧最后一个小于等于up_req的位置
            l = 0, r = i - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (nums[mid] <= up_req) l = mid;
                else r = mid - 1;
            }

            int up_idx = l;
            
            if(up_idx == low_idx){
                if(nums[up_idx] <= up_req && nums[low_idx] >= low_req) ans += 1;
            }else{
                ans += up_idx - low_idx + 1;
            }
            
        }

        return ans;
    }
};

借助函数

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        long long ans = 0;
        int n = nums.size();
        for (int i = 1; i < n; i++) {
            int low_req = lower - nums[i];
            int up_req = upper - nums[i];
            auto left = lower_bound(nums.begin(), nums.begin() + i, low_req);
            auto right = upper_bound(nums.begin(), nums.begin() + i, up_req);
            ans += (right - left);
        }
        return ans;
    }
};

python

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        ans = 0
        nums.sort()
        n = len(nums)

        for i in range(1, n):
            left = bisect_left(nums, lower - nums[i], 0, i)
            right = bisect_left(nums, upper - nums[i], 0, i)

            while right < i and nums[i] + nums[right] == upper:
                right += 1

            ans += right - left

        return ans

复杂度

时间复杂度:$O(n\log N)$ ，每次二分查找耗时，总共执行n次。
空间复杂度: $O(1)$