【Leetcode Daily】2563统计公平数对的数目

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，题目规定了一种公平数对，也就是两个数字之和在一个数值区间中的情况，要求一个数组中有多少个公平数对。

思路分享

• 二分的基本思路可看【Leetcode Daily】34在排序数组中查找元素的第一个和最后一个位置。

• 两数之和，马上就会想到枚举相关的技巧，通过简单变式就能把 l < a + b < r 的条件转化为 l-a < b < r-a，然后只要不断地枚举 a，找出 b 的范围并记录即可。

  https://leetcode.cn/problems/count-the-number-of-fair-pairs/solutions/2107079/er-fen-cha-zhao-de-ling-huo-yun-yong-by-wplbj/

• 由于本题的数对与位置无关，故可以先排序处理。排序后，就可以用二分查找快速定位要查找的数值（b 的区间）。

• 本题学到了 bisect 的后两个参数的作用，即查找下标的区间。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()
        ans = 0
        for i, x in enumerate(nums):
            r = bisect_right(nums, upper - x, 0, i)
            l = bisect_left(nums, lower - x, 0, i)
            ans += r-l
        return ans