统计公平数对的数目.md

统计公平数对的数目

题目描述

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回公平数对的数目。 如果 (i, j) 数对满足以下情况，则认为它是一个公平数对 ： 0 <= i < j < n，且lower <= nums[i] + nums[j] <= upper 示例 1： 输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6 输出：6 解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5)。 示例 2： 输入：nums = [1,7,9,2,5], lower = 11, upper = 11 输出：1 解释：只有单个公平数对：(2,3)。

解题思路

1. 暴力法：两层循环遍历所有可能的数对，判断是否满足条件，时间复杂度为O(n^2)
2. python里面的bisect库

• 首先bisect本质也是对于列表进行二分查找，要用到bisect_left和bisect_right两个函数，前提也是数组按升序排序。
• bisect_left函数是找到一个给定值在有序序列中应该插入的位置，以保持序列的顺序。如果该值已经存在，bisect_left 会返回该值在序列中的第一个位置（即左侧的位置）
• 参数分析，bisect_left(a, x, lo=0, hi=None)，其中a为待查找的列表，x为要查找的值，lo和hi为查找的起始和结束位置，默认为0和None，即整个列表。

    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        # Use __lt__ to match the logic in list.sort() and in heapq
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

• bisect源文件中采用的是左开右闭区间，及[left, right)

    left = bisect_left(nums, lower - x, index)
    right = bisect_right(nums, upper - x, index)
    ans += right - left

• 注意使用bisect_left和bisect_right时，返回的索引值是插入位置，对于返回值，比如说符合条件的index是[0:3]，那么最终bisect_left返回的left是0，bisect_right返回的right是4，所以right - left才是符合条件的数目。

    left = bisect_left(nums, lower - x, index)
    right = bisect_right(nums, upper - x, index)