2563. 统计公平数对的数目-526互联

方法：排序 + 二分

解题思路

（1）先对数组进行排序，排序之后并不影响公平数对的数目；
（2）对于任意一个 \(j\)，它的公平数对 \((i, j)\) 满足 \(lower - nums[j] ≤ nums[i] ≤ upper - nums[j]\)，即在 \([0, j]\) 范围中找满足条件的 \(i\) 的个数，通过二分查找可以快速找到。

代码

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

复杂度分析

时间复杂度：\(O(nlogn)\)；
空间复杂度：\(O(1)\)。