当前位置: 首页 > news >正文

LeetCode题目笔记——2563. 统计公平数对的数目

文章目录

    • 题目描述
    • 题目链接
    • 题目难度——中等
    • 方法一:排序+双指针
      • 代码/Python
      • 代码/C++
    • 方法二
      • 代码/Python
    • 总结

题目描述

这是前天周赛的第二题。

统计公平数对的数目 - 给你一个下标从 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 <= nums.length <= 105
  • nums.length == n
  • -109 <= nums[i] <= 109
  • -109 <= lower <= upper <= 109

题目链接

题目难度——中等

方法一:排序+双指针

  题目说需要统计公平数对的数目,而重点在于这个数目,一开始可能容易被误导将重点放在数对的下标i,j上面,仔细想想会发现我们只需要统计不同的数目就行,不用在乎具体的下标。所以我们可以先将数组排序,然后使用双指针,经过两次遍历,第一次我们统计一下满足上界upper的数对数目,第二次我们统计满足下界lower的数对数目。
  具体的,第一次遍历时,两个指针一前一后,让p2=n-1,p1=0,如果两个数相加大于upper,我们就将p2左移一个位置,直到两个数相加<=upper,则此时从p1到p2之间的数,两两之和都会<=upper,也就有p2-p1个数对满足条件,然后再将p1右移,继续判断,直到p1与p2相遇。第一次遍历时我们只找到了满足上界的下标对,所以我们还要一次类似的遍历来减去多算的小于下界的数对。

代码/Python

class Solution:def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:nums.sort()n = len(nums)res = 0p1, p2 = 0, n - 1while p1 < p2:if nums[p1] + nums[p2] > upper:p2 -= 1else:res += p2 - p1p1 += 1p1, p2 = 0, n - 1while p1 < p2:if nums[p1] + nums[p2] < lower:res -= p2 - p1p1 += 1else:p2 -= 1return res

在这里插入图片描述

代码/C++

class Solution {
public:long long countFairPairs(vector<int>& nums, int lower, int upper) {long long res = 0;int p1, p2, n;sort(nums.begin(), nums.end());n = nums.size();p1 = 0;p2 = n - 1;while(p1 < p2){if(nums[p1] + nums[p2] > upper){p2--;}else{res += p2 - p1;p1++;}}p1 = 0;p2 = n - 1;while(p1 < p2){if(nums[p1] + nums[p2] < lower){res -= p2 - p1;p1++;}else{p2--;}}return res;}
};

方法二

  前面既然已经排好序了,那么我们可以想想是否可以再利用这个有序的性质,比如二分查找。利用二分查找,来加速找到满足条件的下标对,实质上也是方法一的思路。这里贴一个灵茶大佬的题解:灵茶大佬

代码/Python

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

总结

  方法一时间主要在前面排序上,O(NlogN),后面遍历是O(N),所以总的复杂度是(NlogN),空间复杂度 O(1) ,方法二在遍历里面有二分,所以应该是O(N·logN),空间是O(1)。

相关文章:

LeetCode题目笔记——2563. 统计公平数对的数目

文章目录题目描述题目链接题目难度——中等方法一&#xff1a;排序双指针代码/Python代码/C方法二代码/Python总结题目描述 这是前天周赛的第二题。 统计公平数对的数目 - 给你一个下标从 0 开始、长度为 n 的整数数组 nums &#xff0c;和两个整数 lower 和 upper &#xff0c…...

【MySQL Shell】8.9.5 将集群重新加入到 InnoDB ClusterSet

如果 InnoDB 集群是 InnoDB ClusterSet 部署的一部分&#xff0c;MySQL Shell 会在重新启动后立即自动将其恢复到拓扑中的角色&#xff0c;前提是其运行正常且未被标记为无效。但是&#xff0c;如果集群被标记为无效或其 ClusterSet 复制通道已停止&#xff0c;则必须使用 clus…...

元素水平垂直居中的方法有哪些?如果元素不定宽高呢?

实现元素水平垂直居中的方式&#xff1a; 利用定位margin:auto利用定位margin:负值利用定位transformtable布局flex布局grid布局 1-利用定位margin:auto <style>.father{width:500px;height:300px;border:1px solid #0a3b98;position: relative;}.son{width:100px;heig…...

访问学者在新加坡访学生活日常花销大吗?

新加坡地理位置优越&#xff0c;社会发达&#xff0c;教学质量好&#xff0c;吸引不少国内学生前往新加坡留学、访学。那么&#xff0c;去新加坡访学&#xff0c;访问学者花销需要多少钱呢&#xff1f;下面和51访学网小编一起来了解一下吧。 一、饮食 新加坡的饮食从很亲民的…...

XCP实战系列介绍11-几个常用的XCP命令解析

本文框架 1.概述2. 常用命令解析2.1 CONNECT连接(0xFF)2.2 SHORT_UPLOAD 命令(0xF4)2.2 SET_MTA (0xF6)2.3 MOVE命令(0x19)2.4 GET_CAL_PAGE(0xEA)2.5 SET_CAL_PAGE(0xEB)2.6 DOWNLOAD(0xF0)1.概述 在文章《看了就会的XCP协议介绍》中详细介绍了XCP的协议,在《XCP实战系列介绍…...

全志V853芯片 如何在Tina V85x平台切换sensor?

目的 V85x某方案目前默认Sensor是GC2053。实际使用时若需要用到GC4663&#xff08;比如wdr功能&#xff09;和SC530AI&#xff08;支持500W&#xff09;&#xff0c;可按如下步骤完成切换。 步骤 下面以GC4663为例&#xff0c;SC530AI按相应方式适配。 Step1 检查Sensor驱动…...

2023全网最火的接口自动化测试,一看就会

目录 接口自动化测试用例设计Excel接口测试用例访问MySQL接口测试用例访问PyTest测试框架接口自动化测试必备技能-HTTP协议request库实现接口请求 引言 与UI相比&#xff0c;接口一旦研发完成&#xff0c;通常变更或重构的频率和幅度相对较小。因此做接口自动化的性价比更高&…...

华为OD机试真题JAVA实现【最小传递延迟】真题+解题思路+代码(20222023)

🔥系列专栏 华为OD机试(JAVA)真题目录汇总华为OD机试(Python)真题目录汇总华为OD机试(C++)真题目录汇总华为OD机试(JavaScript)真题目录汇总文章目录 🔥系列专栏题目输入输出示例一输入输出说明解题思路核心知识点Code运行结果版权说...

Transformer

Transformer由4部分组成&#xff0c;分别是&#xff1a;输入模块、编码模块、解码模块、输出模块整体架构图&#xff1a;一、输入模块结构 &#xff08;1&#xff09;源文本嵌入层及其位置编码器&#xff08;2&#xff09;目标文本嵌入层及其位置编码器二、编码器模块结构由N个…...

并发包工具之 批量处理任务 CompletionService(异步)、CompletableFuture(回调)

文章目录一、处理异步任务并获取返回值——CompletionService二、线程池三、Callable 与 Future四、通过回调方式处理可组合编排任务——CompletableFuture一、处理异步任务并获取返回值——CompletionService 特点描述&#xff1a; 对于比较复杂的计算&#xff0c;把…...

验收测试分类

α测试 Alpha 是内测版本&#xff0c;即现在所说的CB。 此版本表示该软件仅仅是一个初步完成品, 通常只在软件开发者内部交流, 也有很少一部分发布给专业测试人员。 一般而言, 该版本软件的bug 较多, 普通用户最好不要安装。 β测试 Beta是公测版本&#xff0c;是对所有用户…...

因新硬件支持内核问题Ubuntu 22.04.2推迟发布

导读Ubuntu 22.04.2 LTS 原定于 2 月 9 日发布。但 Canonical 宣布该版本因各种问题不得不推迟两周&#xff0c;定于 2 月 23 日发布。 Ubuntu 22.04.2 LTS 原定于 2 月 9 日发布。但 Canonical 宣布该版本因各种问题不得不推迟两周&#xff0c;定于 2 月 23 日发布。 Canonica…...

agent扩展-自定义外部加载路径

自定义classLoader实现加载外部jar, 以skywalking agent 类加载器为例子 整体思路 扩展findClass &#xff0c;解决loadClass可以查找到扩展findResource&#xff0c;解决getResources可以获取到资源 基本原理 ClassLoader loadClass的加载顺序 findLoadedClass 加载本地已经…...

Elasticsearch使用篇 - 指标聚合

指标聚合 指标聚合从聚合文档中提取出指标进行计算。可以从文档的字段或者使用脚本方式进行提取。 聚合统计可以同时返回明细数据&#xff0c;可以分页查询&#xff0c;可以返回总数量。 可以结合查询条件&#xff0c;限制数据范围&#xff0c;结合倒排索引列式存储。 指标…...

Python生命周期及内存管理

文章目录 一、Python的生命周期 1、概念2、如何监听生命周期二、内存管理 1.存储2.垃圾回收3.引用计数一、生命周期&#xff1a; 1、概念&#xff1a;一个对象从创建到消亡的过程 当一个对象呗创建是&#xff0c;会在内存中分配响应的内存空间进行存储 当这个对象不再使…...

Elasticsearch7.8.0版本进阶——数据写流程

目录一、数据写流程概述二、数据写流程步骤2.1、数据写流程图2.2、数据写流程步骤&#xff08;新建索引和删除文档所需要的步骤顺序&#xff09;2.3、数据写流程的请求参数一、数据写流程概述 新建、删除索引和新建、删除文档的请求都是写操作&#xff0c; 必须在主分片上面完…...

化学试剂Glutaric Acid-PEG-Glutaric Acid,GA-PEG-GA,戊二酸-聚乙二醇-戊二酸

一&#xff1a;产品描述 1、名称 英文&#xff1a;Glutaric Acid-PEG-Glutaric Acid&#xff0c;GA-PEG-GA 中文&#xff1a;戊二酸-聚乙二醇-戊二酸 2、CAS编号&#xff1a;N/A 3、所属分类&#xff1a;Carboxylic acid PEG 4、分子量&#xff1a;可定制&#xff0c; 戊…...

知识图谱业务落地技术推荐之国内知识图谱平台汇总(竞品)[阿里、腾讯、华为等】

各位可以参考国内知识图谱平台产品进行对技术链路搭建和产品参考提供借鉴。...

ABC 289 G - Shopping in AtCoder store 数学推导+凸包

大意&#xff1a; n个顾客&#xff0c;每个人有一个购买的欲望bi,m件物品&#xff0c;每一件物品有一个价值ci,每一个顾客会买商品当且仅当bici>定价. 现在要求对每一个商品定价&#xff0c;求出它的最大销售值&#xff08;数量*定价&#xff09; n,m<2e5 思路&#x…...

ARM Linux 如何在sysfs用户态命令行中控制 GPIO 引脚?

ARM Linux 如何在sysfs用户态命令行中控制 GPIO 引脚&#xff1f;我们在开发工作中&#xff0c;经常需要确定内核gpio驱动&#xff0c;是否有异常&#xff0c;或者在没有应用的情况下&#xff0c;像控制某个外设&#xff0c;这时我们就可以在控制台命令行中&#xff0c;用命令导…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

DAY 45 超大力王爱学Python

来自超大力王的友情提示&#xff1a;在用tensordoard的时候一定一定要用绝对位置&#xff0c;例如&#xff1a;tensorboard --logdir"D:\代码\archive (1)\runs\cifar10_mlp_experiment_2" 不然读取不了数据 知识点回顾&#xff1a; tensorboard的发展历史和原理tens…...