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

2563.统计公平数对的数目

思路

先说一下为什么排序不会影响本道题目的结果，因为本质上是从数组中选择两个数，满足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），而非直接返回下标或元素值

示例
1
2
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()迭代器）
1
lower_bound(v.begin(), v.end(), 2); // 指向第一个2的迭代器（v[2]）

upper_bound

返回第一个 > val 的元素位置：无论是否存在等于val的元素，均返回第一个大于val的元素的迭代器；若所有元素均小于等于val，返回last（容器的end()迭代器）
1
upper_bound(v.begin(), v.end(), 2); // 指向8的迭代器（v[4]）

3. 特殊情况处理

元素不存在时：若序列中无符合条件的元素，两者均返回last（即end()迭代器），表示“结束位置”
1
upper_bound(v.begin(), v.end(), 9); // 返回v.end()（指向末尾后一位置）
元素为最大值时：若val等于最后一个元素的值，upper_bound仍返回end()，而lower_bound返回最后一个元素的迭代器

4. 应用场景

计算元素出现次数：结合upper_bound - lower_bound可快速计算有序序列中某元素的出现次数
1
int count = upper_bound(v.begin(), v.end(), 2) - lower_bound(v.begin(), v.end(), 2);
插入元素保持有序：使用返回的迭代器插入新元素，可维持序列的有序性