力扣2563.统计公平数对的数目
排序 + 二分
-
定一个数 找另一个数的范围
- 当确定 j 时 i的取值范围为[ lower – nums[j] ] ~~ [ upper – nums[j] ]
- 用二分找出合法的位置
- upper_bound是找>k的位置
- lower_bound是找>=k的位置
-
class Solution {public:long long countFairPairs(vector<int>& nums, int lower, int upper) {long long res=0;sort(nums.begin(),nums.end());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]);res += r-l;}return res;}};
多指针
-
因为确定nums[j]后 随着j++,upper - nums[j] 和 lower - nums[j] 一定都在减小
- 所以用双指针倒序搜符合要求的范围
-
class Solution {public:long long countFairPairs(vector<int>& nums, int lower, int upper) {long long res=0;sort(nums.begin(),nums.end());int l=nums.size() , r = l;for(int j=0;j<nums.size();j++){//nums[r-1] <= upper - nums[j]while(r && nums[r-1] > upper - nums[j]) r --;//nums[l-1] < lower - nums[j]while(l && nums[l-1] >= lower - nums[j]) l --;//如果r / l 在j的右侧 代表之后j++会取到这种结果res += min(r,j) - min(l,j);}return res;}};
