Day67 | 灵神 | 二分查找：统计公平数对的数目

Day67 | 灵神 | 二分查找：统计公平数对的数目

2563.统计公平数对的数目

2563. 统计公平数对的数目 - 力扣（LeetCode）

思路

先说一下为什么排序不会影响本道题目的结果，因为本质上是从数组中选择两个数，满足0<i<j<n，lower <= nums[i] + nums[j] <= upper的条件。就算你排序之后，那两个数还是那两个数，无非就是从[1,4]变成了[4,1]而已。

先来说一说错误的，希望大家不要和笔者一样

想的是在二分查找过程中把对数给统计了，check函数也是传入的nums[l],nums[r],lower,upper，按照题目给的条件去比较，然后判断符合条件不符合条件

这时候就发现，我符合条件以后我该往哪边收缩呢？不管往那边收缩都会漏掉情况，往左收缩会漏掉往右的情况，往右收缩会漏掉左边的，同时收缩更不用说了

所以这个时候就该发现自己的思路出了问题

class Solution {
public:
    bool check(long long a,long long b,long long c,long long d)
    {
        if(a+b>=c&&a+b<=d)
            return true;
        return false;
    }
    long long lower_bound(vector<int>& nums,int lower, int upper)
    {
        int l=0,r=nums.size();
        int res=0;
        while(l<r)
        {
            int mid=l+(r-l)/2;
            if(check(nums[l],nums[r],lower,upper))
            {
                res++;
                r=mid;
            }
            else
                l=mid+1;
        }
        return res;
    }
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(),nums.end());
        return lower_bound(nums,lower,upper);
    }
};

正确思路

参考的灵神的思路

用j遍历数组，那么我们的nums[i]需要满足什么条件呢？

lower−nums[j]≤nums[i]≤upper−nums[j]

这时候你就发现呢我们只要用lower-nums[j]去找nums[i]的左边界，用upper-nums[j]去找nums[i]的右边界，那么在左右边界内的数字一定符合条件，也就是数对的数量

不过要注意是在[0,j)这个左开右闭区间进行二分，因为题目说了要i<j

完整代码

笔者的

class Solution {
public:
    int lower_bound(vector<int>&nums,int bound,int target)
    {
        int l=0,r=bound;
        while(l<r)
        {
            int mid=l+(r-l)/2;
            if(nums[mid]>=target)
                r=mid;
            else
                l=mid+1;
        }
        return l;
    }
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(),nums.end());
        long long res=0;
        for(int j=0;j<nums.size();j++)
        {
            // < lower-nums[j] 的 nums[i] 的个数
            int l=lower_bound(nums,j,lower-nums[j]);
            // <= upper-nums[j] 的 nums[i] 的个数
            //这个+1是因为<=x就是(>x+1)的位置-1
            //这里没减1是下面的r-l懒得+1了，减了1就是[l,r]的闭区间，不减就是[l,r)的区间，效果都一样
            int r=lower_bound(nums,j,upper-nums[j]+1);
            res += r- l;
        } 
        return res;
    }
};

灵神的使用二分查找函数的，我觉得都挺好的，多写写二分的算法也不错

class Solution {
public:
    long long countFairPairs(vector<int> &nums, int lower, int upper) {
        sort(nums.begin(),nums.end());
        long long ans = 0;
        for (int j = 0; j < nums.size(); j++) {
            // 注意要在 [0, j) 中二分，因为题目要求两个下标 i < j
            auto r = upper_bound(nums.begin(), nums.begin() + j, upper - nums[j]); // <= upper-nums[j] 的 nums[i] 的个数
            auto l = lower_bound(nums.begin(), nums.begin() + j, lower - nums[j]); // < lower-nums[j] 的 nums[i] 的个数
            ans += r - l;
        }
        return ans;
    }
};

补充知识：upper_bound和lower_bound

upper_bound和lower_bound是C++标准库中用于在已排序序列中查找边界的算法，它们的返回值是迭代器，具体行为如下：

1. 返回值类型

• 返回值为迭代器：两者均返回指向容器中特定位置的迭代器（ForwardIterator或RandomAccessIterator），而非直接返回下标或元素值

  示例

  vector<int> v = {0, 1, 2, 2, 8, 9};
  auto it = upper_bound(v.begin(), v.end(), 2);  // it指向元素8的迭代器（即v[4]）
  

2. 返回值指向的位置

lower_bound

• 返回第一个 ≥ val 的元素位置：若存在等于val的元素，返回第一个等于val的元素的迭代器；若不存在，则返回第一个大于val的元素的迭代器；若所有元素均小于val，返回last（容器的end()迭代器）

  lower_bound(v.begin(), v.end(), 2);  // 指向第一个2的迭代器（v[2]）
  

upper_bound

• 返回第一个 > val 的元素位置：无论是否存在等于val的元素，均返回第一个大于val的元素的迭代器；若所有元素均小于等于val，返回last（容器的end()迭代器）

  upper_bound(v.begin(), v.end(), 2);  // 指向8的迭代器（v[4]）
  

3. 特殊情况处理

• 元素不存在时：若序列中无符合条件的元素，两者均返回last（即end()迭代器），表示“结束位置”

  upper_bound(v.begin(), v.end(), 9);  // 返回v.end()（指向末尾后一位置）
  

• 元素为最大值时：若val等于最后一个元素的值，upper_bound仍返回end()，而lower_bound返回最后一个元素的迭代器

4. 应用场景

• 计算元素出现次数：结合upper_bound - lower_bound可快速计算有序序列中某元素的出现次数

  int count = upper_bound(v.begin(), v.end(), 2) - lower_bound(v.begin(), v.end(), 2);
  

• 插入元素保持有序：使用返回的迭代器插入新元素，可维持序列的有序性

总结

使用时需确保序列已排序，否则结果未定义