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 = 0nums.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 += 1ans += right - leftreturn ans

复杂度

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