力扣2563.统计公平数对的数目

力扣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;
        }
    };