力扣刷题——2563.统计公平数对的数目
题目：
给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。
如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：
0 <= i < j < n，且lower <= nums[i] + nums[j] <= 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) 。
使用排序+二分查找
排序对结果并无影响，因为只是要找到两个数相加大于lower小于upper
由于lower <= nums[i] + nums[j] <= upper，可得
lower-nums[i] <= nums[j] <= upper-nums[i]
我们可以从0开始枚举j，然后在0到j之间二分查找i满足上述公式的（因为i<j),即用
<=upper-nums[j]减去<lower-nums[j]
class Solution {
public:
long long countFairPairs(vector<int>& nums, int lower, int upper) {
ranges::sort(nums);
long long ans=0;
for(int j=0;j<nums.size();j++)
{
auto r=upper_bound(nums.begin(),nums.begin()+j,upper-nums[j]);
auto l=lower_bound(nums.begin(),nums.begin()+j,lower-nums[j]);
ans+=r-l;
}
return ans;
}
};