题目链接:2563. 统计公平数对的数目

这个题求公平对的和在[lower,upper]内.就是数字两两组合,看在不在这个区间,所以答案和数据的顺序就无关,我们可以先进行一个排序.

然后对于$lower\le x+y\le upper$,可以变形为$lower-x\le y \le upper-x$,此时问题就变成了,对于x,在区间[i+1,n],有多少个数出现在[lower-x,upper-x]这个区间.

也就是求L=bisect(a,lower-x-1),R=bisect(a,upper-x)-1

答案就是R-L+1

Python代码如下:

from bisect import *

class Solution:
    def countFairPairs(self, a: List[int], lower: int, upper: int) -> int:
        a.sort()
        res = 0
        for i, x in enumerate(a):
            L = bisect(a, lower - x - 1, i + 1)
            R = bisect(a, upper - x, i + 1) - 1
            res += R - L + 1
        return res

C++代码如下:

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

C++还是需要注意下upper_bound返回的是一个迭代器,不能直接减int型的数字,需要减去数组的起始迭代器得到int型数字,再进行加减.