给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

• 0 <= i < j < n，且
• lower <= nums[i] + nums[j] <= upper

提示：

• 1 <= nums.length <= 105
• nums.length == n
• -109 <= nums[i] <= 109
• -109 <= lower <= upper <= 109

错误解（超时）

class Solution(object):
    def countFairPairs(self, nums, lower, upper):
        count = 0
        n = len(nums)
        for i in range(n):
            for j in range(i+1,n):
                if lower <= nums[i] + nums[j] <= upper:
                    count += 1
        return count

正确解法一（使用python内置的二分库bisect）

from bisect import bisect,bisect_left
class Solution:
    def countFairPairs(self, nums, lower, upper):
        nums.sort()
        count = 0
        n = len(nums)
        for i in range(n):
            u=upper-nums[i]    # l <= nums[j] <= u
            l=lower-nums[i]
            if nums[0]>u:
                break
            if nums[-1]<l:
                continue
            count += max(bisect(nums,u)-max(bisect_left(nums,l),i+1),0)
        return count

正确解法二：

class Solution:
    def countFairPairs(self, nums, lower, upper):
        count = 0
        nums.sort()
        for j, x in enumerate(nums):
            r = bisect_right(nums, upper - x, 0, j)
            l = bisect_left(nums, lower - x, 0, j)
            count += r - l
        return count