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=0
        for j,value in enumerate(nums):
            r=bisect_right(nums,upper-value,0,j)
            l=bisect_left(nums,lower-value,0,j)
            sum+=r-l
        return sum

相关推荐

  1. 2563. 统计公平数目

    2024-06-13 20:54:03       7 阅读
  2. 力扣2563.统计公平数目

    2024-06-13 20:54:03       8 阅读
  3. LeetCode 2824.统计和小于目标下标数目

    2024-06-13 20:54:03       28 阅读
  4. 力扣2799.统计完全子数目

    2024-06-13 20:54:03       10 阅读
  5. (39)统计为偶数数字

    2024-06-13 20:54:03       36 阅读
  6. 算法----K 和最大数目

    2024-06-13 20:54:03       36 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-06-13 20:54:03       16 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-06-13 20:54:03       16 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-06-13 20:54:03       15 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-06-13 20:54:03       18 阅读

热门阅读

  1. 笔记97:C++ 中 string / char 和 int 之间相互转化

    2024-06-13 20:54:03       8 阅读
  2. (2024最新)CentOS 7上在线安装MySQL 5.7|喂饭级教程

    2024-06-13 20:54:03       8 阅读
  3. cuda 架构设置

    2024-06-13 20:54:03       6 阅读
  4. 【npm如何发布自己的插件包】

    2024-06-13 20:54:03       6 阅读
  5. chat gpt基本原理解读

    2024-06-13 20:54:03       10 阅读
  6. 标准化数据

    2024-06-13 20:54:03       6 阅读
  7. 使用nmcli命令创建、删除bond

    2024-06-13 20:54:03       6 阅读
  8. 《阅读的方法》读后感——超越期待的收获

    2024-06-13 20:54:03       5 阅读
  9. 华为数通——奇偶数子网划分与流量控制(QoS)

    2024-06-13 20:54:03       7 阅读
  10. 中介子方程十四

    2024-06-13 20:54:03       4 阅读
  11. 仲恺ZK——信计专业《软件体系结构》复习总结

    2024-06-13 20:54:03       6 阅读