【Leetcode 每日一题 - 补卡】1534. 统计好三元组
问题背景
给你一个整数数组 a r r arr arr,以及 a 、 b 、 c a、b 、c a、b、c 三个整数。请你统计其中好三元组的数量。
如果三元组 ( a r r [ i ] , a r r [ j ] , a r r [ k ] ) (arr[i], arr[j], arr[k]) (arr[i],arr[j],arr[k]) 满足下列全部条件,则认为它是一个 好三元组 。
- 0 ≤ i < j < k < a r r . l e n g t h 0 \le i < j < k < arr.length 0≤i<j<k<arr.length
- ∣ a r r [ i ] − a r r [ j ] ∣ ≤ a |arr[i] - arr[j]| \le a ∣arr[i]−arr[j]∣≤a
- ∣ a r r [ j ] − a r r [ k ] ∣ ≤ b |arr[j] - arr[k]| \le b ∣arr[j]−arr[k]∣≤b
- ∣ a r r [ i ] − a r r [ k ] ∣ ≤ c |arr[i] - arr[k]| \le c ∣arr[i]−arr[k]∣≤c
其中 ∣ x ∣ |x| ∣x∣ 表示 x x x 的绝对值。
返回 好三元组的数量 。
数据约束
- 3 ≤ a r r . l e n g t h ≤ 100 3 \le arr.length \le 100 3≤arr.length≤100
- 0 ≤ a r r [ i ] ≤ 1000 0 \le arr[i] \le 1000 0≤arr[i]≤1000
- 0 ≤ a , b , c ≤ 1000 0 \le a, b, c \le 1000 0≤a,b,c≤1000
解题过程
题中要求的约束有三个,暴力枚举的时间复杂度是 O ( N 3 ) O(N ^ 3) O(N3)。
如果数组是有序的,那可以很容易地提高时间方面的效率,但是结果与元素的初始位置有关,所以不方便直接排序。
退而求其次,定义一个下标数组,对它进行排序。
然后将数组中的元素当作 j j j 来遍历,将满足 ∣ a r r [ i ] − a r r [ j ] ∣ ≤ a |arr[i] - arr[j]| \le a ∣arr[i]−arr[j]∣≤a 以及 ∣ a r r [ j ] − a r r [ k ] ∣ ≤ b |arr[j] - arr[k]| \le b ∣arr[j]−arr[k]∣≤b
两个条件的原数组中的元素分别记录到哈希表中。
接下来只要再求满足第三个条件的元素对的数量,根据绝对值的定义,可以在线性的时间内得到合法结果的上下限。
具体实现
class Solution {public int countGoodTriplets(int[] arr, int a, int b, int c) {Integer[] idx = new Integer[arr.length];Arrays.setAll(idx, i -> i);Arrays.sort(idx, (i, j) -> arr[i] - arr[j]);int res = 0;for (int j : idx) {int cur = arr[j];List<Integer> list1 = new ArrayList<>();for (int i : idx) {if (i < j && Math.abs(arr[i] - cur) <= a) {list1.add(arr[i]);}}List<Integer> list2 = new ArrayList<>();for (int k : idx) {if (k > j && Math.abs(arr[k] - cur) <= b) {list2.add(arr[k]);}}int left = 0;int right = 0;for (int item : list1) {while (right < list2.size() && list2.get(right) <= item + c) {right++;}while (left < list2.size() && list2.get(left) < item - c) {left++;}res += right - left;}}return res;}
}
相关文章:
【Leetcode 每日一题 - 补卡】1534. 统计好三元组
问题背景 给你一个整数数组 a r r arr arr,以及 a 、 b 、 c a、b 、c a、b、c 三个整数。请你统计其中好三元组的数量。 如果三元组 ( a r r [ i ] , a r r [ j ] , a r r [ k ] ) (arr[i], arr[j], arr[k]) (arr[i],arr[j],arr[k]) 满足下列全部条件ÿ…...
医疗设备预测性维护合规架构:从法规遵循到技术实现的深度解析
在医疗行业数字化转型加速推进的当下,医疗设备预测性维护已成为提升设备可用性、保障医疗安全的核心技术。然而,该技术的有效落地必须建立在严格的合规框架之上。医疗设备直接关乎患者生命健康,其维护过程涉及医疗法规、数据安全、质量管控等…...
如何在 IntelliJ IDEA 中安装 FindBugs-IDEA 1.0.1
以下是 FindBugs-IDEA 1.0.1 插件在 IntelliJ IDEA 中的安装步骤(适用于较旧版本的 IDEA,新版本可能需使用替代插件如 SpotBugs): 方法一:手动下载安装(适用于无法通过市场安装的情况) 下载插件…...
小车正常但是加载不出地图 找不到mapserver
Request for map failed; trying again... 找不到mapserver 原因: bash [ERROR] [1744895448.714854952]: failed to open image file "/home/liyb/catkin_ws/src/nav_demo/map/crossing.pgm": Couldnt open /home/xxx/catkin_ws/src/nav_demo/map/cr…...
无头开发模式
“无头”开发模式(Headless Development Mode)是指在没有直接连接物理显示器(monitor)、键盘或鼠标等输入输出设备的情况下,通过远程工具(如 SSH、SCP、rsync、VNC 或 Web 界面)对设备进行开发、…...
DAY 47 leetcode 232--栈与队列.用栈实现队列
题号232 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): class MyQueue {Stack<Integer> stackIn;Stack<Integer> stackOut;/** Initialize your data structure here. */pu…...
SpringAI+DeepSeek大模型应用开发——4 对话机器人
目录 项目初始化 pom文件 配置模型 ChatClient 同步调用 流式调用 日志功能 对接前端 解决跨域 会话记忆功能 ChatMemory 添加会话记忆功能 会话历史 管理会话id 保存会话id 查询会话历史 完善会话记忆 定义可序列…...
leetcode0058. 最后一个单词的长度-easy
1 题目:最后一个单词的长度 官方标定难度:易 给你一个字符串 s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。 示例 1&#x…...
深入理解 Linux top 命令:从字段解读到性能诊断
系统或产品都需要部署到服务器或容器上运行,而服务器的运行效率直接影响到系统的稳定性和用户体验。因此,服务器的性能监控与分析就显得尤为重要。 在实际运维和性能测试过程中,我们可以从以下关键的几个方面入手进行系统监控与分析(网络延迟分析暂时先略过): CPU 使用率…...
[特殊字符] UnionFS(联合文件系统)原理解析:容器背后的存储技术
🔍 UnionFS(联合文件系统)原理解析:容器背后的存储技术 💡 什么是 UnionFS? UnionFS(联合文件系统) 是一种可以将多个不同来源的文件系统“合并”在一起的技术。它的核心思想是&am…...
部署若依前后端分离
参考部署:https://blog.csdn.net/qq_46073825/article/details/128716794?spm1001.2014.3001.5502 1.连接mysql(windows版本) 2.更新数据库用户为远程可连接 3.redis下载地址 https://github.com/tporadowski/redis/releases 5执行npm init 或者npm install --r…...
用Python Pandas高效操作数据库:从查询到写入的完整指南
一、环境准备与数据库连接 1.1 安装依赖库 pip install pandas sqlalchemy psycopg2 # PostgreSQL # 或 pip install pandas sqlalchemy pymysql # MySQL # 或 pip install pandas sqlalchemy # SQLite 1.2 创建数据库引擎 通过SQLAlchemy创建统一接口:…...
eventBus 事件中心管理组件间的通信
EventBus(事件总线)是Vue中用于实现非父子组件间通信的轻量级方案,通过一个中央Vue实例管理事件的发布与订阅。 一、基本使用步骤 1.创建EventBus实例 推荐单独创建文件(如event-bus.js)导出实例,避免全…...
某客户ORA-600 导致数据库反复重启问题分析
上班期间,收到业务反馈,测试环境数据库连接报错。 查看数据库alert日志,发现从中午的时候就出现了重启。并且在17时20分左右又发生了重启: 同时,在重启前alert日志中出现了ORA-600报错,相关报错在trc文件中…...
LeetCode 2176.统计数组中相等且可以被整除的数对:两层遍历模拟
【LetMeFly】2176.统计数组中相等且可以被整除的数对:两层遍历模拟 力扣题目链接:https://leetcode.cn/problems/count-equal-and-divisible-pairs-in-an-array/ 给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k ,请你返回满足…...
Vue项目Webpack Loader全解析:从原理到实战配置指南
Vue项目Webpack Loader全解析:从原理到实战配置指南 前言 在Vue项目的开发与构建中,Webpack Loader扮演着资源转换的核心角色。无论是单文件组件(SFC)的解析、样式预处理,还是静态资源的优化,都离不开Loa…...
Vscode --- LinuxPrereqs │远程主机可能不符合 glibc 和 libstdc++ Vs code 服务器的先决条件
打开vscode连接远程linux服务器,发现连接失败,并出现如下报错信息: 原因是: vscode 官网公告如下:2025 年 3 月 (版本 1.99) - VSCode 编辑器 版本1.97 官网公告如下:链接 版本1.98 官网公告如下&am…...
大数据常见的模型定义及应用场景建议╮(╯▽╰)╭
以下是常见的大数据模型类型及其分析方法: 1. 描述性模型 1.1 定义 描述性模型:用于描述数据的现状和历史趋势,帮助理解数据的特征和模式。 1.2 常见模型 统计摘要:均值、中位数、标准差等。数据可视化:直方图、散…...
红宝书第四十八讲:实时通信双雄:Socket.IO Meteor 的奇妙旅程
红宝书第四十八讲:实时通信双雄:Socket.IO & Meteor 的奇妙旅程 资料取自《JavaScript高级程序设计(第5版)》。 查看总目录:红宝书学习大纲 一、实时通信基础 1. WebSocket与HTTP对比 传统HTTP请求类似送信&…...
【数字图像处理】图像分割(1)
图像分割定义 把图像分成若干个特定的、具有独特性质的区域,并提出感兴趣目标的技术和过程 图像分割概述 一幅图像通常是由代表物体的图案与背景组成,简称物体与背景 图像分割的本质:将图像按照区域内的一致性和区域间的不一致性进行分类的过…...
VFlash的自动化和自定义动作
文章目录 一、automation 自动化二、custom actions 自定义动作常用方法如何选择要发送的诊断请求CustomActionValueList 作用Pre Action和Post Action之间交换信息 提示:如何打印软件中变量报错:无法打开源文件 Windows.h stdio.h conio.h报错ÿ…...
pytorch学习02
自动微分 自动微分模块torch.autograd负责自动计算张量操作的梯度,具有自动求导功能。自动微分模块是构成神经网络训练的必要模块,可以实现网络权重参数的更新,使得反向传播算法的实现变得简单而高效。 1. 基础概念 张量 Torch中一切皆为张…...
TV板卡维修技术【四】
【一】热成像松香的结合快速定位短路位置 发现电路短路,但是无法定位到大概位置,可以采用烧机法: 热成像大致定位,松香准确定位: 可以很快找到这种小陶瓷电容短路的故障: 测量电路是否有大短路,…...
Rust生命周期、文件与IO
文章目录 Rust生命周期生命周期注释结构体如何使用字符串静态生命周期 Rust文件与IO接收命令行参数命令行输入文件读取文件写入 Rust生命周期 终于讲到Rust最重要的机制之一了,生命周期机制 我们先复习一下垂悬引用 {let r;{let x 5;r &x;}println!("…...
22、字节与字符的概念以及二者有什么区别?
1、概念 字节(byte) 定义:字节是计算机信息技术中用于计量存储容量和传输容量的一种单位,通常由8个二进制位(bit)组成。 作用:字节是计算机存储和处理信息的基本单位,用于衡量数据…...
APP端测试
一、功能测试 1. 核心测试点 安装/卸载/升级:验证不同安装方式(应用商店/APK/IPA) 注册登录:多种登录方式测试(手机号、第三方账号) 核心业务流程:支付流程、内容发布等关键路径 中断测试&a…...
Langchain-构建向量数据库和检索器
向量数据库安装 pip install langchain-chroma 文档》向量存储》向量数据库。 和0416 提示词工程相同。 初始化 import osfrom langchain_chroma import Chroma from langchain_community.chat_message_histories import ChatMessageHistory from langchain_core.documents im…...
PPT无法编辑怎么办?原因及解决方法全解析
在日常办公中,我们经常会遇到需要编辑PPT的情况。然而,有时我们会发现PPT文件无法编辑,这可能由多种原因引起。今天我们来看看PPT无法编辑的几种常见原因,并提供实用的解决方法,帮助你轻松应对。 原因1:文…...
PH热榜 | 2025-04-17
1. Mailgo 标语:一款利用人工智能的冷邮件平台,能够提升邮件送达率。 介绍:Mailgo将AI线索寻找助手、智能日程安排和预热账户集成到一个直观的平台上——帮助销售团队和创业者高效到达客户邮箱,轻松扩展业务,并加快转…...
maptalks矩形绘制结束后,获取最大经度最大纬度,最小经度最小纬度,从左上角开始依次获取并展示坐标
maptalks矩形绘制结束后,获取最大经度最大纬度,最小经度最小纬度,从左上角开始依次获取并展示坐标 重点 // 获取绘制的矩形图形对象const rectangle param.geometry;// 获取矩形外接矩形范围(西南角/东北角坐标)cons…...
网页图像优化:现代格式与响应式技巧
网页图像优化:现代格式与响应式技巧 网页图像如果处理不好,很容易拖慢加载速度,影响用户体验。这篇文章聊聊怎么用现代图像格式和响应式技巧,让你的网站图片加载更快、效果更好。 推荐的图像格式 选对图像格式,能在保…...
python中参数前**的含义
在Python中,参数前的 ** 表示该参数是一个“关键字参数”或者说是“可变关键字参数”。这种参数允许函数接受任意数量的关键字参数,并将这些参数存储在一个名为**kwargs的字典中。这使得函数可以接收任意数量的键值对参数,这在编写需要处理多…...
内存编码手册:整数与浮点数的二进制世界
1.整数在内存中的存储 之前在学习操作符的博文中,我们就已经学习了整数在内存中存储的一些基本知识,我们来快速回忆一下,并开始学习新的知识。 之前的学习中,我们知道整数的二进制表示方法有三种,即原码,…...
铷元素的市场供需情况如何?
铷元素的市场供需格局呈现出显著的稀缺性与战略价值,其供应高度依赖锂矿开采的副产品,而需求则随着高科技产业的快速发展持续攀升。以下从供应、需求、价格、政策及可持续性五个维度展开分析: 一、供应端:资源稀缺与技术瓶颈并存…...
MATLAB 程序实现了一个层次化光网络的数据传输模拟系统
% 主程序 num_pods = 4; % Pod 数量 num_racks_per_pod = 4; % 每个 Pod 的 Rack 数量 num_nodes_per_rack = 4; % 每个 Rack 的 Node 数量 max_wavelength = 50; % 可用波长数(根据冲突图动态调整) num_packets = 1000; % 模拟的…...
LFI to RCE
LFI不止可以来读取文件,还能用来RCE 在多道CTF题目中都有LFItoRCE的非预期解,下面总结一下LFI的利用姿势 1. /proc/self/environ 利用 条件:目标能读取 /proc/self/environ,并且网页中存在LFI点 利用方式: 修改请…...
QT6 源(34):随机数生成器类 QRandomGenerator 的源码阅读
(1)代码来自 qrandom.h ,结合官方的注释: #ifndef QRANDOM_H #define QRANDOM_H#include <QtCore/qalgorithms.h> #include <algorithm> // for std::generate #include <random> // for std::mt1993…...
极狐GitLab GEO 功能介绍
极狐GitLab 是 GitLab 在中国的发行版,关于中文参考文档和资料有: 极狐GitLab 中文文档极狐GitLab 中文论坛极狐GitLab 官网 Geo (PREMIUM SELF) Geo 是广泛分布的开发团队的解决方案,可作为灾难恢复策略的一部分提供热备份。Geo 不是 开箱…...
快速上手,OceanBase + MCP + LLM,搭建 AI 应用
在 AI 技术发展的进程中,大语言模型(LLM)凭借卓越的信息处理与推理能力广受重视。然而,数据孤岛问题仍是 LLM 面临的核心挑战。目前,LLM 的推理主要依赖于预先训练的数据和有限的上下文窗口,既无法动态访问…...
【Python爬虫基础篇】--1.基础概念
目录 1.爬虫--定义 2.爬虫--组成 3.爬虫--URL 1.爬虫--定义 网络爬虫,是一种按照一定规则,自动抓取互联网信息的程序或者脚本。另外一些不常使用的名字还有蚂蚁、自动索引、模拟程序或者蠕虫。随着网络的迅速发展,万维网成为大量信息的载体…...
Linux :进程替换
进程替换 (一)进程程序替换1.替换原理2.替换函数exec函数命名理解 (二)实现简易shell (一)进程程序替换 1.替换原理 用fork创建子进程后执行的是和父进程相同的程序(但有可能执行不同的代码分支),子进程往…...
XC7K410T‑2FFG900I 赛灵思XilinxFPGA Kintex‑7
XC7K410T‑2FFG900I Xilinx 赛灵思FPGA Kintex‑7 系列定位:Kintex‑7 中端,高性价比与高性能平衡 工艺节点:28 nm HPL(High‑Performance, Low‑Power)HKMG(High‑κ Metal Gate) 逻辑资源&…...
list容器介绍及模拟实现和与vector比较
目录 list容器介绍 lisy接口 list迭代器的注意事项 迭代器失效 list的模拟实现 list的节点 list的迭代器实现 list的接口实现 vector和list的优缺点 vector优点: vector缺点: list优点: list缺点: 总结: …...
[图论]Prim
Prim 本质:BFS贪心,对点进行操作。与最短路Dijkstra算法是“孪生兄弟”。存储结构:链式前向星适用对象:可为负权图,可求最大生成树核心思想:最近的邻接点一定在最小生成树(MST)上,对点的最近邻…...
【python】pysharm常用快捷键使用-(1)
*1.格式化代码【Ctrl Alt L】 写代码的时候会有很多黄色的波浪号(如图)又叫蚂蚁线,可以点击任意黄色波浪号的代码,然后按下【Ctrl Alt L】进行代码格式化。 2.添加函数功能和参数注释 添加函数文档字符串 docstring 在函数…...
06-DevOps-自动构建Docker镜像
前面已经完成了jar文件的打包和发布,但在实际使用时,可能会遇到外部依赖环境发生改变,为了解决这些问题,更多的做法是把应用程序以docker镜像,生成容器的方式运行,这是一种标准化的方式。 创建Dockerfile文…...
案例驱动的 IT 团队管理:创新与突破之路:第五章 创新管理:从机制设计到文化养成-5.2 技术决策民主化-5.2.2技术选型的量化评估矩阵
👉 点击关注不迷路 👉 点击关注不迷路 👉 点击关注不迷路 文章大纲 案例驱动的 IT 团队管理:创新与突破之路 - 第五章 创新管理:从机制设计到文化养成 - 5.2 技术决策民主化5.2.2 技术选型的量化评估矩阵一、技术选型的…...
力扣面试150题--有效的字母异位词和字母异位词分组
Day 24 题目描述 思路 初次思路:如果两个字符串为异位词,说明它们长度相同并且字母出现的次数相同,于是有以下做法: 定义一个map,来保存s中每个字符的出现次数处理特殊情况,如果长度不同,直接…...
WSL2-Ubuntu22.04安装URSim5.21.3
WSL2-Ubuntu22.04安装URSim5.21.3 准备安装启动 准备 名称版本WSL2Ubuntu22.04URSim5.21.3VcXsrvNaN WSL2安装与可视化请见这篇:WSL2-Ubuntu22.04-配置。 安装 我们是wsl2-ubuntu22.04,所以安装Linux版本的URSim,下载之前需要注册一下,即…...
配合 Spring Bean 注入,把 Function 管理起来?
大家好呀!今天我们来聊聊一个特别有意思的话题 - 如何在Spring中优雅地管理和注入Function对象。就像把各种调料整齐地摆在厨房里一样,我们要把各种函数方法也管理得井井有条!🍳 一、为什么要把Function管起来?&#…...