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

LeetCode每日一题4.19

news 来源：原创 2025/8/6 22:25:18

2563. 统计公平数对的数目

题目

在这里插入图片描述

问题分析

输入：一个整数数组 nums 和两个整数 lower 和 upper。
输出：返回满足条件的公平数对的数目，即对于所有 0 <= i < j < n，lower <= nums[i] + nums[j] <= upper 的数对 (i, j) 的数量。

思路

方法一：暴力解法（时间复杂度 O(n^2)）
直接遍历所有可能的数对 (i, j) 并检查它们是否满足条件。
方法二：优化解法（二分查找）
排序：首先对数组 nums 进行排序。
遍历：然后对每个 nums[i]，使用二分查找来找到满足条件的 nums[j]（其中 j > i）的范围。
二分查找：分别找到满足 nums[i] + nums[j] <= upper 的最大 j（通过 find_upper_bound）和满足 nums[i] + nums[j] >= lower 的最小 j（通过 find_lower_bound）。

代码

class Solution:def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:# 对数组进行排序nums.sort()count = 0n = len(nums)for i in range(n):# 找到满足 nums[i] + nums[j] <= upper 的最大 j 的位置r = self.find_upper_bound(nums, upper - nums[i], i + 1, n - 1)# 找到满足 nums[i] + nums[j] >= lower 的最小 j 的位置l = self.find_lower_bound(nums, lower - nums[i], i + 1, n - 1)# 统计符合条件的数对数量if l <= r:count += r - l + 1return countdef find_upper_bound(self, nums, target, start, end):while start <= end:mid = (start + end) // 2if nums[mid] > target:end = mid - 1else:start = mid + 1return enddef find_lower_bound(self, nums, target, start, end):while start <= end:mid = (start + end) // 2if nums[mid] < target:start = mid + 1else:end = mid - 1return start

复杂度分析

时间复杂度：
排序：(O(n \log n))
遍历并二分查找：(O(n \log n))
因此，最终时间复杂度为：
[ O(n \log n) + O(n \log n) = O(n \log n) ]
空间复杂度：
遍历：(O(n))

学习

排序

排序是为了后续能够利用二分查找来高效地找到满足条件的 nums[j]。

遍历

for i in range(n):r = self.find_upper_bound(nums, upper - nums[i], i + 1, n - 1)l = self.find_lower_bound(nums, lower - nums[i], i + 1, n - 1)if l <= r:count += r - l + 1

遍历每个 nums[i]：对于每个 nums[i]，我们需要找到所有 j > i 且满足 lower <= nums[i] + nums[j] <= upper 的 nums[j]。
找到 r 和 l：
r 是满足 nums[i] + nums[j] <= upper 的最大 j 的位置。
l 是满足 nums[i] + nums[j] >= lower 的最小 j 的位置。
统计数对：如果 l <= r，则 l 到 r 之间的所有 j 都是符合条件的，因此数对数量为 r - l + 1。

二分查找

find_upper_bound：找到第一个大于 target 的元素的位置（返回该位置的前一个位置）。

  def find_upper_bound(self, nums, target, start, end):while start <= end:mid = (start + end) // 2if nums[mid] > target:end = mid - 1else:start = mid + 1return end

find_lower_bound：找到第一个不小于 target 的元素的位置。

  def find_lower_bound(self, nums, target, start, end):while start <= end:mid = (start + end) // 2if nums[mid] < target:start = mid + 1else:end = mid - 1return start

与相向双指针方法的区别

相向双指针方法的典型特点是：
两个指针从两端向中间移动：一个指针从数组的起始位置开始（left），另一个指针从数组的末尾位置开始（right）。
根据当前 nums[left] + nums[right] 的值来决定移动哪个指针：
如果当前和小于 lower，则 left 指针右移。
如果当前和大于 upper，则 right 指针左移。
如果当前和在 [lower, upper] 范围内，则统计符合条件的数对并调整指针。

LeetCode每日一题4.19

2563. 统计公平数对的数目题目问题分析输入：一个整数数组 nums 和两个整数 lower 和 upper。输出：返回满足条件的公平数对的数目，即对于所有 0 < i < j < n，lower < nums[i] nums[j] < upper 的数对 (i, j)…...

编程日记 2025/8/6 22:25:18

Spring AI 开发 - 快速入门

先看效果项目搭建 Spring AI 是 Spring 推出的一个项目，目标是提供统一的API抽象层，屏蔽不同AI模型和服务的底层差异，实现跨平台兼容性。演示使用的模型是阿里的 qwq-32b。环境要求： JDK ：17以上（包括…...

编程日记 2025/8/2 13:56:37

leetcode哈希表（六）-三数相加

题目 15. 三数之和给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k ，同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复…...

编程日记 2025/8/1 10:45:52

Photoshop安装与配置--简单攻略版

下载地址:Photoshop软件工具下载安装完成后，即可运行Photoshop.exe；打开工具页面后，按照下面简单配置即可 1.编辑-》首选项-》常规或者直接快捷键CtrlK 暂存盘：一定要设置为非C盘 2.性能 3.文件处理以上配置比较基础&#xf…...

编程日记 2025/8/2 13:56:37

一个 CTO 的深度思考

今天和一些同事聊了一会，以下是我的观点我的观点，成年人只能筛选，不能培养在组织中，应该永远向有结果的人看齐。不能当他站出来讲话的时候，大家还要讨论讨论，他虽然拿到结果了，但是他就是有一…...

编程日记 2025/8/5 17:50:03

Java：使用Maven构建项目无src解决方案

创建箭头所指的包和类以及yml文件： 类中： package com.itheima;import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication;SpringBootApplication public class BigEventApplication …...

编程日记 2025/8/5 11:45:47

Git 命令速查手册

听说用美图可以钓读者？ 一、基础操作核心命令 1. 仓库初始化与克隆命令作用示例git init创建新仓库git init my-projectgit clone克隆远程仓库git clone [https://github.com/user/repo.git](https://github.com/user/repo.git)git remote add关联远程仓库git re…...

编程日记 2025/8/4 14:49:19

office软件中word里面的编号库和列表库功能

在Microsoft Word中，编号库和列表库是两大核心排版工具，分别服务于不同层级的文档结构化需求。以下从功能定义、核心差异、应用场景及操作技巧等维度进行详细解析：一、编号库（Numbering Library） 1. 定义与功能编号库是Word中预设或用户自定义的有序列表格式集合，用于…...

编程日记 2025/8/5 4:34:43

C++入门七式——模板初阶

目录函数模板函数模板概念函数模板格式函数模板的原理函数模板的实例化模板参数的匹配原则类模板类模板的定义格式类模板的显式实例化当面对下面的代码时，大家会不会有一种无力的感觉？明明这些代码差不多，只是因为类型不…...

编程日记 2025/7/31 6:55:13

Python+Selenium+Pytest+POM自动化测试框架封装（完整版）

🍅 点击文末小卡片 ，免费获取软件测试全套资料，资料在手，涨薪更快 1、测试框架简介 1）测试框架的优点代码复用率高，如果不使用框架的话，代码会显得很冗余。可以组装日志、报告、邮件等一…...

编程日记 2025/8/3 10:18:56

matlab 处理海洋数据并画图的工具包--ocean_data_tools

matlab 处理海洋数据并画图的工具包–ocean_data_tools matlab 处理海洋数据并画图的工具包–ocean_data_tools ocean_data_tools 简化了提取、格式化和可视化免费可用的海洋学数据的过程。虽然可以在线访问大量海洋学数据，但由于获取这些数据并将其格式化为可用数据…...

编程日记 2025/8/6 5:07:14

软件开发指南——GUI 开发方案推荐

1. LVGL (Light and Versatile Graphics Library) 适用场景：嵌入式设备、资源受限环境优势： 专为嵌入式设计的开源 GUI 库，内存占用极小（最低仅需 64KB RAM）支持触摸屏、硬件加速（如 STM32 的 LTDC&…...

编程日记 2025/8/5 4:50:57

JDK8 HashMap的实现原理

一 HashMap底层存储结构 HashMap底层结构采用（数组）（链表 or 红黑树）的形式来存储节点。首先HashMap是一个数组，而且数组里面每个位置可以放入多个元素，形象一点，咱们把数组的这些个位置称为桶…...

编程日记 2025/8/6 22:25:18

YOLO拓展-锚框(anchor box)详解

一.锚框（anchor box）概述 1.1什么是锚框锚框就是一种进行预测的像素框，通过遍历输入图像上所有可能的像素框，然后选出正确的目标框，并对位置和大小进行调整就可以完成目标检测任务。对于yolo锚框的建设须基于实际…...

编程日记 2025/8/4 19:49:34

U-Boot（Universal Bootloader）简介

U-Boot 是一种开源的、高度可定制的引导加载程序（Bootloader），专为嵌入式系统和特定硬件平台设计。它负责在设备上电后初始化硬件、加载操作系统内核，并将控制权移交给操作系统，是嵌入式设备启动过程中不可或缺的核心…...

编程日记 2025/7/30 5:54:23

turtle库绘制进阶图形

要求： 1.绘制嵌套彩色五角星（大小逐层递减） 2. 设计函数绘制自定义正多边形（边数与颜色参数化） 3. 扩展：实现动态旋转花瓣图案代码： import turtledef draw_nested_star():colors ["…...

编程日记 2025/8/3 5:10:25

[matlab]南海地形眩晕图代码

[matlab]南海地形眩晕图代码请ChatGPT帮写个南海地形眩晕图代码图片图片代码 .rtcContent { padding: 30px; } .lineNode {font-size: 12pt; font-family: "Times New Roman", Menlo, Monaco, Consolas, "Courier New", monospace; font-style: n…...

编程日记 2025/8/4 17:37:36

3. 进程概念

目录 1. 冯诺依曼体系结构 2. 操作系统 3. 理解进程的一般思路 4. 查看进程 5. fork初识 6. 进程状态 6.1 一般操作系统 6.2 Linux系统是怎么维护进程状态的 7. 进程优先级先谈硬件-再谈软件-最后谈进程。 1. 冯诺依曼体系结构我们常见的计算机（笔记本电…...

编程日记 2025/8/6 22:22:54

yolov8的数据处理lableimg的安装以及使用

视频数据集准备 video cv2.VideoCapture("./BVN.mp4") num 0 # 计数器 save_step 30 # 间隔帧 while True:rel, frame video.read()if not ret:breaknum 1if num % save_step 0:cv2.imwrite("./demo images/" str(num) ".jpg", frame)l…...

编程日记 2025/8/2 13:38:50

小刚说C语言刷题——1035 判断成绩等级

1.题目描述输入某学生成绩，如果 86分以上(包括 86分）则输出 VERY GOOD ，如果在 60到 85之间的则输出 GOOD (包括 60和 85)，小于 60 的则输出 BAD。输入输入只有一行，包括 1个整数。输出输出只有一行&#xf…...

编程日记 2025/8/3 1:55:03

Spring 依赖冲突解决方案详解

引言在Spring框架中，依赖管理是一个核心功能，它使得开发者能够轻松地管理应用程序中的各种组件和服务。然而，随着项目的增长和复杂度的增加，依赖冲突问题也变得日益常见。本文将详细介绍Spring中不同类型的依赖冲突及其解决方法…...

编程日记 2025/8/2 21:35:21

P11299 [NOISG 2021 Finals] Fraud 题解

题目背景你被任命为第 24 届全国信息学奥林匹克竞赛的负责人！ 题目描述本次竞赛共有 N 名参赛者和 2 轮比赛。第 i 名参赛者在第一轮获得了分，在第二轮获得了分。每轮比赛分别有一个正整数权重 X 和 Y。第 i 名参赛者的最终得分计算公式为&a…...

编程日记 2025/7/28 13:32:27

AI时代下你需要和想要了解的英文缩写含义

在AI智能时代下，越来愈多的企业都开始重视并应用以及开发AI相关产品，这个时候都会或多或少的涉及到英文，英文还好，但是如果是缩写，如果我们没有提前了解过，我们往往很难以快速Get到对方的意思。在这里&…...

编程日记 2025/8/1 18:15:38

大数据平台简介

一、分布式系统基础架构 （一）定义与核心特征分布式系统是由多台计算机（节点）通过网络协作组成的系统，对外表现为一个统一整体。其核心特征包括： 去中心化：节点平等或分角色协作（如…...

编程日记 2025/8/6 2:01:25

电脑端移植至手机平板：攻克难题，仙盟架构显神通——仙盟创梦IDE

在将电脑端应用移植到手机和平板的过程中，常面临诸多棘手问题。像 1.x 号关闭按钮因位置设计欠佳，难以被用户精准点击，字体过小导致阅读与操作不便等。未来之窗仙盟创梦凭借创新的仙盟架构，巧妙且高效地化解了这些困扰开发者与用户…...

编程日记 2025/7/31 18:45:36

基于Python的中国象棋小游戏的设计与实现

基于Python的中国象棋小游戏的设计与实现第一章绪论1.1 研究背景1.2 研究意义第二章需求分析2.1 需求分析2.1.1核心功能需求2.1.2 用户体验需求2.1.3 衍生功能需求 2.2 可行性分析2.2.1 技术可行性2.2.2 经济可行性2.2.3 市场可行性2.2.4 法律与合规性第三章概要设计3.1 …...

编程日记 2025/8/2 19:36:11

HCIP --- OSPF综合实验

一、拓扑图二、实验要求 1，R5为ISP，其上只能配置IP地址;R4作为企业边界路由器，出口公网地址需要通过PPP协议获取，并进行chap认证。 2，整个0SPF环境IP基于172.16.0.8/16划分。 3，所有设备均可访问R5的环…...

编程日记 2025/8/4 1:28:34

【OpenGL】OpenGL学习笔记-1：VS2019配置OpenGL开发环境

在Visual Studio 2019中可以通过手动配置库文件或NuGet包管理器快速安装的方法配置OpenGL环境，详细步骤如下： 一、打开VS2019，创建新的控制台项目二、方法一：手动配置GLEW/GLFW/GLAD库 GLFW是窗口管理和输入事件的基础设施&…...

编程日记 2025/8/6 22:22:55

GWAS_LD

局部LDblock 绘图 1. 查看显著位点附近基因情况链接pvalue显著位点文件 ln -s ~/yiyaoran/GWAS/my_GWAS_J/P3.GWAS/01.tassel/mlm_output.manht_figure.sigSite.out . #也可以自己筛选awk $2 9 && $4 < 0.000028481 mlm_output.manht_input>368_GWAS.snpsnp两…...

编程日记 2025/8/2 13:36:39

WinForms开发基础：实现带X按钮的ClearableTextBox控件

前言我们经常看到这样的带X按钮的输入框如果使用WinForms开发中，该如何进行设计，普通的TextBox控件如何进行改造？为了提升用户体验，在TextBox文本框内添加一个“x”按钮，方便用户一键清除内容。本文将介绍如何通过继…...

编程日记 2025/8/6 22:22:56

直线轴承常规分类知多少？

直线轴承的分类方式多样，以下是从材质、结构形状和常规系列三个维度进行的具体分类： 按主要材质分类外壳材质：常见的有不锈钢，具有良好的耐腐蚀性，适用于一些对环境要求较高、易受腐蚀的工作场景；轴承…...

编程日记 2025/8/6 8:20:49

算法期末复习

算法期末复习 1.单选题 \1. 二分搜索算法是利用( A)实现的算法。 A. 分治策略 B. 动态规划法 C. 贪心法 D. 回溯法 \2. 回溯法解旅行售货员问题时的解空间树时( C ) 。 A. 子集树 B. 深度优先生成树 C. 排序树 D. 广度优先生成树 \3. 下列算法中通常以自底向上的方式求解最…...

编程日记 2025/8/5 14:13:04

LeetCode 5：最长回文子串

1、题目描述给你一个字符串 s，找到 s 中最长的回文子串。示例 1: 输入：s "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。示例 2: 输入：s "cbbd" 输出&#…...

编程日记 2025/8/1 5:31:13

2025年4月19日记录大模型出现的计算问题

2025年4月19日记录大模型出现的计算问题，用了四个大模型计算json的数值，3个错误，1个正确问题 Class Train Val answer 2574 853 screen 5025 1959 blackBoard 7847 3445 teacher 8490 3228 stand…...

编程日记 2025/7/26 16:22:58

Python语法系列博客 · 第3期数据结构入门（列表、元组、字典、集合）

上一期小练习解答（第2期回顾） ✅ 练习1：判断一个数是正数、负数还是零 num float(input("请输入一个数：")) if num > 0:print("正数") elif num < 0:print("负数") else:print("零&q…...

编程日记 2025/8/4 1:25:03

【对Linux文件权限的深入理解】

Linux文件权限 Linux下权限概念概念相关命令 Linux的文件权限管理1.文件访问者的分类（⼈）文件类型和访问权限（事物属性）文件权限值的表示方法⽂件访问权限的相关设置方法目录的权限（比较重要）粘滞位 Linux下…...

编程日记 2025/8/2 22:11:25

2025.04.19【Spider】| 蜘蛛图绘制技巧精解

Basic multi-group radar chart Start with a basic version, learn how to format your input dataset Radar chart with ggradar A Spider chart made using the ggradar package and a lot of customization.A work by Tuo Wang 文章目录 Basic multi-group radar chartRa…...

编程日记 2025/8/3 4:29:57

2563. 统计公平数对的数目

题目

问题分析

思路

代码

复杂度分析

学习

排序

遍历

二分查找

与相向双指针方法的区别

相关文章：