题目链接

Leetcode.2563 统计公平数对的数目 Rating ： 1721

题目描述

给你一个下标从 0开始、长度为 n的整数数组 nums，和两个整数 lower和 upper，返回 公平数对的数目 。

如果 (i, j)数对满足以下情况，则认为它是一个 公平数对 ：

• 0<=i
• lower<=nums[i]+nums[j]<=upperlower <= nums[i] + nums[j] <= upperlower<=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) 。

提示：

• 1<=nums.length<=1051 <= nums.length <= 10^51<=nums.length<=105
• nums.length==nnums.length == nnums.length==n
• −109<=nums[i]<=109-10^9 <= nums[i] <= 10^9−109<=nums[i]<=109
• −109<=lower<=upper<=109-10^9 <= lower <= upper <= 10^9−109<=lower<=upper<=109

分析：

观察题意我们可以得出，nums[i]和nums[j]的顺序其实可以交换，即 i和j的顺序并不重要。

所以我们可以对 nums进行 升序排序。

我们对其做一下转换 lower<=nums[i]+nums[j]<=upperlower <= nums[i] + nums[j] <= upperlower<=nums[i]+nums[j]<=upper

lower−nums[j]<=nums[i]<=upper−nums[j]lower - nums[j] <= nums[i] <= upper - nums[j]lower−nums[j]<=nums[i]<=upper−nums[j]

即对于 每一个j（0≤j[lower - nums[j] , upper - nums[j]]的范围有多大即可，然后加到答案 ans上。

时间复杂度： O(n∗logn)O(n * logn)O(n∗logn)

C++代码：

using LL = long long;
class Solution {
public:long long countFairPairs(vector& nums, int lower, int upper) {int n = nums.size();sort(nums.begin(),nums.end());LL ans = 0;for(int j = 0;j < n;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;}
};

Java代码：

class Solution {public long countFairPairs(int[] nums, int lower, int upper) {int n = nums.length;Arrays.sort(nums);long ans = 0;for(int j = 0;j < n;j++){//求 大于upper - nums[j] 的 rightint t = upper - nums[j];int l = 0;int r = j;while(lint mid = (l + r) >> 1;if(nums[mid] > t) r = mid;else l = mid + 1;} int right = r;//求 大于等于 lower - nums[j] 的 leftt = lower - nums[j];l = 0;r = j;while(l < r){int mid = (l + r)>>1;if(nums[mid] >= t) r = mid;else l = mid + 1;}int left = l;ans += right - left;}return ans;}
}