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

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...