【力扣每日一题】存在重复元素 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内…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
