【力扣每日一题】存在重复元素 II 解题思路
219. 存在重复元素 II 解题思路
问题描述
给定一个整数数组 nums 和一个整数 k,要求判断数组中是否存在两个 不同的索引 i 和 j,使得:
nums[i] == nums[j]- 且满足
abs(i - j) <= k
如果满足上述条件,返回 true,否则返回 false。
示例
示例 1:
输入:nums = [1,2,3,1], k = 3
输出:true
示例 2:
输入:nums = [1,0,1,1], k = 1
输出:true
示例 3:
输入:nums = [1,2,3,1,2,3], k = 2
输出:false
提示
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^90 <= k <= 10^5
解题思路
这道题可以通过哈希表来实现高效的查找。我们需要检查数组中是否存在两个相同的元素,其索引差值不超过 k。一个直观的做法是利用哈希表记录每个数字上次出现的位置,并与当前索引进行比较。
详细步骤:
- 使用一个字典
last来存储每个数字最近一次出现的索引。 - 遍历
nums数组中的每个元素,对于每个元素:- 如果当前数字已经出现在字典中,计算当前索引与上次索引的差值。
- 如果差值小于等于
k,直接返回True,表示满足条件。 - 如果差值大于
k,更新字典中该数字的最新索引为当前索引。
- 如果遍历结束后没有找到符合条件的两个元素,返回
False。
时间复杂度分析:
- 遍历数组的时间复杂度是 O(n),其中 n 是数组
nums的长度。 - 哈希表的插入和查找操作平均时间复杂度是 O(1)。
- 因此,总时间复杂度为 O(n)。
空间复杂度分析:
- 需要使用哈希表来存储数字和对应的索引,最坏情况下哈希表中可能存储 n 个元素,因此空间复杂度是 O(n)。
代码实现
class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:last = {}for i, x in enumerate(nums):if x in last and abs(last[x] - i) <= k:return Truelast[x] = ireturn False
代码解释:
last = {}:初始化一个空字典,用于存储数字及其最近的索引。for i, x in enumerate(nums)::遍历数组nums,i是索引,x是当前元素。if x in last and abs(last[x] - i) <= k::检查当前数字x是否在字典last中,如果在,计算当前索引i与上次索引last[x]之间的差值。如果差值小于等于k,返回True。last[x] = i:更新字典last中数字x的最新索引。return False:遍历结束后如果没有满足条件的元素,返回False。
边界情况
- 数组长度为 1:如果数组只有一个元素,显然不可能有两个不同的索引满足条件,应该直接返回
False。 - k = 0:如果
k为 0,表示要求两个相同的数字索引是完全相同的,因此当nums中有重复元素时,返回True,否则返回False。
总结
这道题考察了如何使用哈希表进行高效查找。通过记录每个元素上次出现的索引,并在遍历过程中进行条件判断,我们能够在 O(n) 的时间复杂度内完成任务,避免了暴力解法中 O(n^2) 的性能瓶颈。
相关文章:
【力扣每日一题】存在重复元素 II 解题思路
219. 存在重复元素 II 解题思路 问题描述 给定一个整数数组 nums 和一个整数 k,要求判断数组中是否存在两个 不同的索引 i 和 j,使得: nums[i] nums[j]且满足 abs(i - j) < k 如果满足上述条件,返回 true,否则…...
React第二十八章(css modules)
css modules 什么是 css modules 因为 React 没有Vue的Scoped,但是React又是SPA(单页面应用),所以需要一种方式来解决css的样式冲突问题,也就是把每个组件的样式做成单独的作用域,实现样式隔离,而css modules就是一种…...
本地运行大模型效果及配置展示
电脑上用ollama安装了qwen2.5:32b,deepseek-r1:32b,deepseek-r1:14b,llama3.1:8b四个模型,都是Q4_K_M量化版。 运行过程中主要是cpu和内存负载比较大,qwen2.5:32b大概需要22g,deepseek-r1:32b类…...
愿景:做机器视觉行业的颠覆者
一个愿景,两场战斗,专注制胜。 一个愿景:做机器视觉行业的颠覆者。 我给自己创业,立一个大的愿景:做机器视觉行业的颠覆者。 两场战斗:无监督-大模型 上半场,无监督。2025-2030,共五…...
arm-linux-gnueabihf安装
Linaro Releases windows下打开wsl2中的ubuntu,资源管理器中输入: \\wsl$gcc-linaro-4.9.4-2017.01-x86_64_arm-linux-gnueabihf.tar.xz 复制到/home/ark01/tool 在 Ubuntu 中创建目录: /usr/local/arm,命令如下: …...
力扣动态规划-16【算法学习day.110】
前言 ###我做这类文章一个重要的目的还是给正在学习的大家提供方向(例如想要掌握基础用法,该刷哪些题?建议灵神的题单和代码随想录)和记录自己的学习过程,我的解析也不会做的非常详细,只会提供思路和一些关…...
Java基础知识总结(三十四)--java.util.Date
月份从0-11; /* 日期对象和毫秒值之间的转换。 1,日期对象转成毫秒值。Date类中的getTime方法。 2,如何将获取到的毫秒值转成具体的日期呢? Date类中的setTime方法。也可以通过构造方法。 */ //日期对象转成毫秒值 Date …...
零售EDI:Costco EDI 项目须知
Costco 是全球领先的会员制仓储式零售商,致力于为会员提供高品质且价格实惠的商品。其经营范围涵盖食品、电子产品、家居用品、服装和办公设备等多个领域。 Costco 的 EDI 对接需求分析 为了更高效地管理其复杂的全球供应链,Costco 采用了先进的 EDI&am…...
最近最少使用算法(LRU最近最少使用)缓存替换算法
含义 最近最少使用算法(LRU)是一种缓存替换算法,用于在缓存空间有限的情况下,选择最少使用的数据项进行替换。该算法的核心思想是基于时间局部性原理,即刚被访问的数据在未来也很有可能被再次访问。 实现 LRU算法的…...
sublime_text的快捷键
sublime_text的快捷键 向下复制, 复制光标所在整行并插入到下一行:通过 CtrlShiftD 实现快速复制当前行的功能。 可选多行, 不选则复制当前行 ctrl Shift D 删除当前行:通过 CtrlShiftK 实现快速删除当前行的功能。 可选多行, 不选则删当前行 ctrl S…...
使用Pygame制作“贪吃蛇”游戏
贪吃蛇 是一款经典的休闲小游戏:玩家通过操控一条会不断变长的“蛇”在屏幕中移动,去吃随机出现的食物,同时要避免撞到墙壁或自己身体的其他部分。由于其逻辑相对简单,但可玩性和扩展性都不错,非常适合作为新手练习游戏…...
本地部署DeepSeek开源多模态大模型Janus-Pro-7B实操
本地部署DeepSeek开源多模态大模型Janus-Pro-7B实操 Janus-Pro-7B介绍 Janus-Pro-7B 是由 DeepSeek 开发的多模态 AI 模型,它在理解和生成方面取得了显著的进步。这意味着它不仅可以处理文本,还可以处理图像等其他模态的信息。 模型主要特点:Permalink…...
Java开发vscode环境搭建
1 几个名词 JDK Java Development Kit JRE Java Runtion Environment JVM JDK 包括 Compiler,debugger,JRE等。JRE包括JVM和Runtime Library。 2 配置环境 2.1 安装JDK 类比 C/C的 g工具 官网:https://www.oracle.com/java/technologies/downloads/ 根据自己使…...
深入解析:一个简单的浮动布局 HTML 示例
深入解析:一个简单的浮动布局 HTML 示例 示例代码解析代码结构分析1. HTML 结构2. CSS 样式 核心功能解析1. 浮动布局(Float)2. 清除浮动(Clear)3. 其他样式 效果展示代码优化与扩展总结 在网页设计中,浮动…...
车载软件 --- 大一新生入门汽车零部件嵌入式开发
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 简单,单纯,喜欢独处,独来独往,不易合同频过着接地气的生活…...
DDD - 领域驱动设计分层架构:构建可演化的微服务架构
文章目录 引言1. 什么是DDD分层架构?1.1 DDD分层架构的演变1.2 四层架构的起源与问题1.3 依赖倒置和五层架构 2. DDD分层架构的核心层次2.1 用户接口层(User Interface Layer)2.2 应用层(Application Layer)2.3 领域层…...
2025数学建模美赛|赛题翻译|E题
2025数学建模美赛,E题赛题翻译 更多美赛内容持续更新中......
DeepSeek-V3 与 DeepSeek R1 对比分析:技术与应用的全面解析
一、背景 在当今科技飞速发展的时代,深度学习技术如同一股强大的浪潮,席卷了自然语言处理(NLP)、计算机视觉(CV)以及多模态模型等众多领域。从智能语音助手到图像识别技术,从文本生成工具到多模…...
qt-Quick3D笔记之官方例程Runtimeloader Example运行笔记
qt-Quick3D笔记之官方例程Runtimeloader Example运行笔记 文章目录 qt-Quick3D笔记之官方例程Runtimeloader Example运行笔记1.例程运行效果2.例程缩略图3.项目文件列表4.main.qml5.main.cpp6.CMakeLists.txt 1.例程运行效果 运行该项目需要自己准备一个模型文件 2.例程缩略图…...
Linux内核中的页面错误处理机制与按需分页技术
在现代操作系统中,内存管理是核心功能之一,而页面错误(Page Fault)处理机制是内存管理的重要组成部分。当程序访问一个尚未映射到物理内存的虚拟地址时,CPU会触发页面错误异常,内核需要捕获并处理这种异常,以决定如何响应,例如加载缺失的页面、处理权限错误等。Linux内…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...
