2563. 统计公平数对的数目

本文主要是介绍2563. 统计公平数对的数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

给你一个下标从 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. 目标是求解两个不等式0 <= i < j < n和
   lower <= nums[i] + nums[j] <= upper
   我们可以简化变量化为只关于nums[i]的一个不等式
   lower-nums[j]<=nums[i]<=upper-nums[j]
   那么怎么实现呢？
   我们可以这么想：
   我们可以求利用bisect_right函数来求上边界即 nums[i]<= upper-nums[j]的个数
   再利用bisect_left函数来求下边界即 lower-nums[j]<=nums[i]的个数
   两者一减就是 符合不等式的nums[i]的个数即也是公平对的对数

语法知识：

r=bisect_right(nums,upper-value,0,j)：
是在nums[0]-nums[j]中的范围中找寻比upper-nums[j]中大的元素的下标，这里的nums[j]用当前的值value替代

代码：

class Solution(object):def countFairPairs(self, nums, lower, upper):nums.sort()//对数组进行排序sum=0for j,value in enumerate(nums):r=bisect_right(nums,upper-value,0,j)l=bisect_left(nums,lower-value,0,j)sum+=r-lreturn sum

这篇关于2563. 统计公平数对的数目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---