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

【力扣每日一题】存在重复元素 II 解题思路

219. 存在重复元素 II 解题思路

问题描述

给定一个整数数组 nums 和一个整数 k,要求判断数组中是否存在两个 不同的索引 ij,使得:

  • 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^9
  • 0 <= k <= 10^5

解题思路

这道题可以通过哈希表来实现高效的查找。我们需要检查数组中是否存在两个相同的元素,其索引差值不超过 k。一个直观的做法是利用哈希表记录每个数字上次出现的位置,并与当前索引进行比较。

详细步骤:

  1. 使用一个字典 last 来存储每个数字最近一次出现的索引。
  2. 遍历 nums 数组中的每个元素,对于每个元素:
    • 如果当前数字已经出现在字典中,计算当前索引与上次索引的差值。
    • 如果差值小于等于 k,直接返回 True,表示满足条件。
    • 如果差值大于 k,更新字典中该数字的最新索引为当前索引。
  3. 如果遍历结束后没有找到符合条件的两个元素,返回 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

代码解释:

  1. last = {}:初始化一个空字典,用于存储数字及其最近的索引。
  2. for i, x in enumerate(nums)::遍历数组 numsi 是索引,x 是当前元素。
  3. if x in last and abs(last[x] - i) <= k::检查当前数字 x 是否在字典 last 中,如果在,计算当前索引 i 与上次索引 last[x] 之间的差值。如果差值小于等于 k,返回 True
  4. last[x] = i:更新字典 last 中数字 x 的最新索引。
  5. return False:遍历结束后如果没有满足条件的元素,返回 False

边界情况

  • 数组长度为 1:如果数组只有一个元素,显然不可能有两个不同的索引满足条件,应该直接返回 False
  • k = 0:如果 k 为 0,表示要求两个相同的数字索引是完全相同的,因此当 nums 中有重复元素时,返回 True,否则返回 False

总结

这道题考察了如何使用哈希表进行高效查找。通过记录每个元素上次出现的索引,并在遍历过程中进行条件判断,我们能够在 O(n) 的时间复杂度内完成任务,避免了暴力解法中 O(n^2) 的性能瓶颈。

相关文章:

【力扣每日一题】存在重复元素 II 解题思路

219. 存在重复元素 II 解题思路 问题描述 给定一个整数数组 nums 和一个整数 k&#xff0c;要求判断数组中是否存在两个 不同的索引 i 和 j&#xff0c;使得&#xff1a; nums[i] nums[j]且满足 abs(i - j) < k 如果满足上述条件&#xff0c;返回 true&#xff0c;否则…...

React第二十八章(css modules)

css modules 什么是 css modules 因为 React 没有Vue的Scoped&#xff0c;但是React又是SPA(单页面应用)&#xff0c;所以需要一种方式来解决css的样式冲突问题&#xff0c;也就是把每个组件的样式做成单独的作用域&#xff0c;实现样式隔离&#xff0c;而css modules就是一种…...

本地运行大模型效果及配置展示

电脑上用ollama安装了qwen2.5:32b&#xff0c;deepseek-r1:32b&#xff0c;deepseek-r1:14b&#xff0c;llama3.1:8b四个模型&#xff0c;都是Q4_K_M量化版。 运行过程中主要是cpu和内存负载比较大&#xff0c;qwen2.5:32b大概需要22g&#xff0c;deepseek-r1&#xff1a;32b类…...

愿景:做机器视觉行业的颠覆者

一个愿景&#xff0c;两场战斗&#xff0c;专注制胜。 一个愿景&#xff1a;做机器视觉行业的颠覆者。 我给自己创业&#xff0c;立一个大的愿景&#xff1a;做机器视觉行业的颠覆者。 两场战斗&#xff1a;无监督-大模型 上半场&#xff0c;无监督。2025-2030&#xff0c;共五…...

arm-linux-gnueabihf安装

Linaro Releases windows下打开wsl2中的ubuntu&#xff0c;资源管理器中输入&#xff1a; \\wsl$gcc-linaro-4.9.4-2017.01-x86_64_arm-linux-gnueabihf.tar.xz 复制到/home/ark01/tool 在 Ubuntu 中创建目录&#xff1a; /usr/local/arm&#xff0c;命令如下&#xff1a; …...

力扣动态规划-16【算法学习day.110】

前言 ###我做这类文章一个重要的目的还是给正在学习的大家提供方向&#xff08;例如想要掌握基础用法&#xff0c;该刷哪些题&#xff1f;建议灵神的题单和代码随想录&#xff09;和记录自己的学习过程&#xff0c;我的解析也不会做的非常详细&#xff0c;只会提供思路和一些关…...

Java基础知识总结(三十四)--java.util.Date

月份从0-11&#xff1b; /* 日期对象和毫秒值之间的转换。 1&#xff0c;日期对象转成毫秒值。Date类中的getTime方法。 2&#xff0c;如何将获取到的毫秒值转成具体的日期呢&#xff1f; Date类中的setTime方法。也可以通过构造方法。 */ //日期对象转成毫秒值 Date …...

零售EDI:Costco EDI 项目须知

Costco 是全球领先的会员制仓储式零售商&#xff0c;致力于为会员提供高品质且价格实惠的商品。其经营范围涵盖食品、电子产品、家居用品、服装和办公设备等多个领域。 Costco 的 EDI 对接需求分析 为了更高效地管理其复杂的全球供应链&#xff0c;Costco 采用了先进的 EDI&am…...

最近最少使用算法(LRU最近最少使用)缓存替换算法

含义 最近最少使用算法&#xff08;LRU&#xff09;是一种缓存替换算法&#xff0c;用于在缓存空间有限的情况下&#xff0c;选择最少使用的数据项进行替换。该算法的核心思想是基于时间局部性原理&#xff0c;即刚被访问的数据在未来也很有可能被再次访问。 实现 LRU算法的…...

sublime_text的快捷键

sublime_text的快捷键 向下复制, 复制光标所在整行并插入到下一行&#xff1a;通过 CtrlShiftD 实现快速复制当前行的功能。 可选多行, 不选则复制当前行 ctrl Shift D 删除当前行&#xff1a;通过 CtrlShiftK 实现快速删除当前行的功能。 可选多行, 不选则删当前行 ctrl S…...

使用Pygame制作“贪吃蛇”游戏

贪吃蛇 是一款经典的休闲小游戏&#xff1a;玩家通过操控一条会不断变长的“蛇”在屏幕中移动&#xff0c;去吃随机出现的食物&#xff0c;同时要避免撞到墙壁或自己身体的其他部分。由于其逻辑相对简单&#xff0c;但可玩性和扩展性都不错&#xff0c;非常适合作为新手练习游戏…...

本地部署DeepSeek开源多模态大模型Janus-Pro-7B实操

本地部署DeepSeek开源多模态大模型Janus-Pro-7B实操 Janus-Pro-7B介绍 Janus-Pro-7B 是由 DeepSeek 开发的多模态 AI 模型&#xff0c;它在理解和生成方面取得了显著的进步。这意味着它不仅可以处理文本&#xff0c;还可以处理图像等其他模态的信息。 模型主要特点: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工具 官网&#xff1a;https://www.oracle.com/java/technologies/downloads/ 根据自己使…...

深入解析:一个简单的浮动布局 HTML 示例

深入解析&#xff1a;一个简单的浮动布局 HTML 示例 示例代码解析代码结构分析1. HTML 结构2. CSS 样式 核心功能解析1. 浮动布局&#xff08;Float&#xff09;2. 清除浮动&#xff08;Clear&#xff09;3. 其他样式 效果展示代码优化与扩展总结 在网页设计中&#xff0c;浮动…...

车载软件 --- 大一新生入门汽车零部件嵌入式开发

我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&#xff1a; 简单&#xff0c;单纯&#xff0c;喜欢独处&#xff0c;独来独往&#xff0c;不易合同频过着接地气的生活…...

DDD - 领域驱动设计分层架构:构建可演化的微服务架构

文章目录 引言1. 什么是DDD分层架构&#xff1f;1.1 DDD分层架构的演变1.2 四层架构的起源与问题1.3 依赖倒置和五层架构 2. DDD分层架构的核心层次2.1 用户接口层&#xff08;User Interface Layer&#xff09;2.2 应用层&#xff08;Application Layer&#xff09;2.3 领域层…...

2025数学建模美赛|赛题翻译|E题

2025数学建模美赛&#xff0c;E题赛题翻译 更多美赛内容持续更新中......

DeepSeek-V3 与 DeepSeek R1 对比分析:技术与应用的全面解析

一、背景 在当今科技飞速发展的时代&#xff0c;深度学习技术如同一股强大的浪潮&#xff0c;席卷了自然语言处理&#xff08;NLP&#xff09;、计算机视觉&#xff08;CV&#xff09;以及多模态模型等众多领域。从智能语音助手到图像识别技术&#xff0c;从文本生成工具到多模…...

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内…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...