leetcode 2563. 统计公平数对的数目

题目如下

数据范围

显然数组长度最大可以到10的5次方n方的复杂度必然超时，阅读题目实际上就是寻找两个位置不同的数满足不等式即可(实际上i j无所谓是哪个 我们只要把位置小的想成i就行)。
按照上面的思路我们只需要排序数组然后从前往后遍历数组然后利用二分查找寻找下界和上界的下标然后把下标相减就能得到答案。
值得注意的是这样计算会把结果翻倍（假设 1,2满足答案那么按照我们的算法1,2 2,1都会被统计所以结果要减半）

通过代码

class Solution {
public:
    int findlow(vector<int>& nums, int v, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        int mid;
        while (l < r) {
            mid = (l + r) / 2;
            if (nums[mid] + v >= target) {
                r = mid;
            } else{
                l = mid + 1;
            }
        }
        if(nums[l] + v < target)return -1;
      //  cout << l;
        return l;
    }
    int findhigh(vector<int>& nums,int v, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        int mid;
        while (l < r) {
            mid = (l + r + 1) / 2;
            if (nums[mid] + v > target) {
                r = mid - 1;
            } else{
                l = mid;
            }
        }
        if(nums[l] + v > target)return -1;
        return l;
    }
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        long long ans = 0;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int low, high;
        for (int i = 0; i < n; i++) {
            low = findlow(nums,nums[i],lower);
            high = findhigh(nums,nums[i],upper);
            if(low != -1 && high != -1){
                ans += high - low;
              //  cout << low << "-" << high << "\n";
                if(i < low || i > high){
                    ans++;
                }
            }
        }
        return ans/2;
    }
};