当前位置: 首页 > 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内…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

Pydantic + Function Calling的结合

1、Pydantic Pydantic 是一个 Python 库&#xff0c;用于数据验证和设置管理&#xff0c;通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发&#xff08;如 FastAPI&#xff09;、配置管理和数据解析&#xff0c;核心功能包括&#xff1a; 数据验证&#xff1a;通过…...

React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构

React 实战项目&#xff1a;微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇&#xff01;在前 29 篇文章中&#xff0c;我们从 React 的基础概念逐步深入到高级技巧&#xff0c;涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...