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

【面试经典150 | 哈希表】存在重复元素 II

文章目录

  • Tag
  • 题目来源
  • 题目解读
  • 解题思路
    • 方法一:哈希表
    • 方法二:滑动窗口
  • 其他语言
    • python3+哈希表
    • python3+滑动窗口
  • 写在最后

Tag

【哈希表】【滑动窗口】【数组】


题目来源

219. 存在重复元素 II


题目解读

判断在数组中有没有相同的元素小于一定的距离。


解题思路

方法一:哈希表

我们维护一个哈希表来记录数组中的元素以及上一次出现的位置,如果上一次出现的位置和这一次出现的位置之差小于等于 k,那就返回 true,否则返回 false

实现代码

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {int n = nums.size();unordered_map<int, int> mp;for (int i = 0; i < n; ++i) {if (mp.count(nums[i]) && (i - mp[nums[i]] <= k)) {return true;}mp[nums[i]] = i;}return false;}
};

复杂度分析

时间复杂度: O ( n ) O(n) O(n) n n n 为数组 nums 的长度。

空间复杂度: O ( n ) O(n) O(n),使用哈希表记录数组中元素上一次出现的位置。

方法二:滑动窗口

换一个思路,我们只要判断在长度为 k 的窗口中是否有重复的元素出现即可。在滑窗没满之前,就向滑窗中加入元素,加入之前判断滑窗内是否有当前要加入的元素,如果有,直接返回 false;当滑窗满了,滑动滑窗,当前的 nums[i] 要进入滑窗,那么 nums[i - k - i] 要退出滑窗,判断滑窗内是否有当前要加入的元素,如果有,直接返回 false

如果滑窗滑到数组末尾,都没有返回 true,就返回 false

实现代码

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_set<int> s;int n = nums.size();for (int i = 0; i < n; ++i) {if (i > k) {s.erase(nums[i - k - 1]);}if (s.count(nums[i])) return true;s.emplace(nums[i]);}return false;}
};

时间复杂度: O ( n ) O(n) O(n) n n n 为数组 nums 的长度。

空间复杂度: O ( k ) O(k) O(k),使用无序集合记录滑窗中的元素。


其他语言

python3+哈希表

class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:pos = {}for i, num in enumerate(nums):if num in pos and i - pos[num] <= k:return Truepos[num] = ireturn False

python3+滑动窗口

class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:s = set()for i, num in enumerate(nums):if i > k:s.remove(nums[i - k - 1])if num in s:return Trues.add(num)return False

写在最后

如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。

最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。

相关文章:

【面试经典150 | 哈希表】存在重复元素 II

文章目录 Tag题目来源题目解读解题思路方法一&#xff1a;哈希表方法二&#xff1a;滑动窗口 其他语言python3哈希表python3滑动窗口 写在最后 Tag 【哈希表】【滑动窗口】【数组】 题目来源 219. 存在重复元素 II 题目解读 判断在数组中有没有相同的元素小于一定的距离。 解…...

Intellij 安装配置 lombok

Intellij 安装配置 lombok 用 lombok 能够减少 setter/getter/noArgsConstructor 这样的 boilerplate 代码&#xff0c;所以用起来还是比较方便的。 刚开始以为直接安装到 maven 里面就能用了&#xff0c;运行的时候发现 Getter, Data 这些 annotation 根本找不到&#xff0c…...

Chrome插件精选 — 暗色主题插件

Chrome实现同一功能的插件往往有多款产品&#xff0c;逐一去安装试用耗时又费力&#xff0c;在此为某一类型插件记录下比较好用的一款或几款&#xff0c;便于节省尝试的时间和精力。 Dark Reader 下载地址 (访问密码: 8276) Dark Reader是一款浏览器扩展程序&#xff0c;用于…...

PXE解决uefi安装centos6黑屏问题

解决pxe安装centos6黑屏 author: 铁乐与猫 date:2021.12.10 背景 主板&#xff1a;supermicr SBI-4129P-T3N System InformationManufacturer: SupermicroProduct Name: SBI-4129P-T3NVersion: 123456789Serial Number: S264322X9905439UUID: 00000000-0000-0000-0000-AC1…...

Feign 调用为何POST不支持同时传入多个SpringQueryMap对象,但是GET方法就支持?

Feign 调用为何POST不支持同时传入多个SpringQueryMap对象&#xff0c;但是GET方法就支持&#xff1f; 1.1 问题背景1.2 原因分析1.3 修复方案1.3.1 修复方案一 切换使用GET方法&#xff0c;可以试用多个SpringQueryMap注解 &#xff08;测试实际不行&#xff09;1.3.2 修复方案…...

RISC-V 特权级架构

特权级别 级别的数值越大&#xff0c;特权级越高&#xff0c;掌控硬件的能力越强&#xff0c;在CPU硬件层面&#xff0c;M模式必须存在&#xff0c;其它模式可以不存在 执行环境调用 ecall &#xff0c;这是一种很特殊的陷入类的指令&#xff0c; 相邻两特权级软件之间的接口正…...

目录启示:PHP 与命名空间的声明

文章目录 参考环境命名空间概念版本支持影响范围 全局命名空间概念魔术常量 \_\_NAMESPACE\_\_声明全局命名空间 声明命名空间为空间命名命名规则核心命名空间 子命名空间的声明在同一文件中定义多个命名空间无括号命名空间声明有括号命名空间声明禁止混合使用推荐使用有括号命…...

D. Divide and Equalize--Codeforces Round 903 (Div. 3)

D. Divide and Equalize 题意&#xff1a;让一组数中的一个数除以一个因子&#xff0c;一个数除以一个因子&#xff0c;假如经过若干次操作后能够使数组所有数相等&#xff0c;那么输出YES&#xff0c;否则输出NO。 分析&#xff1a;乘除因子&#xff0c;那么实际上就是因子的…...

保姆式教程:MAC安装Android studio(包括安装JDK,Android SDK),解决gradle下载慢的问题

文章目录 参考文章安装JDK并配置环境变量安装JDK配置JDK相关的环境变量 Android studio 安装下载Android studiogradle下载慢解决方法 安装Android SDK选择jdk版本安装SDK并配置环境变量 参考文章 原文链接 原文链接 安装JDK并配置环境变量 安装JDK 下载地址 下载后双击安装…...

Ps:选区的布尔运算

选区的布尔 Boolean运算指的是选区之间的相加&#xff08;并集&#xff09;、相减&#xff08;差集&#xff09;以及相交&#xff08;交集&#xff09;&#xff0c;从而形成一个新的选区。 ◆ ◆ ◆ 使用工具选项栏 在 Ps 中&#xff0c;几乎所有的选区工具的工具选项栏上都有…...

PyTorch 深度学习之卷积神经网络(基础篇)Basic CNN(九)

0. Revision: Fully connected Neural Network 全连接 1. Convolution Neural Network 保留空间信息 1.1 Convolution Convolution-Single Input Channel 单通道 数乘 3 input Channels 3通道 N input Channels N input Channels and M output channel M 个卷积核 1.2 conv…...

torch实现Gated PixelCNN

文章目录 PixelCNNGated PixelCNN PixelCNN import torch import torch.nn as nn import torch.nn.functional as F# Pixel CNNclass MaskConv2d(nn.Module):def __init__(self, conv_type, *args, **kwags):super().__init__()assert conv_type in (A, B)self.conv nn.Conv2…...

破局「二次创业」:合思的新解法

在新的水温下&#xff0c;寻找更为良性的发展正在成为企业的必答题。对此&#xff0c;合思给出的不仅是一份更“省”的答题方法。也更是从认知层到行动层&#xff0c;最后到工具层的一张授人以渔的“渔网”。 作者|思杭 编辑|皮爷 出品|产业家 今年4月初&#xff0c;广州…...

第五章:TCP和UDP基本原理

TCP和UDP基本原理 一、TCP/IP传输层的作用二、 端口1.范围2. 服务端3. 客户端4. 常见知名端口号4.1 TCP 80 HTTP4.2 TCP 20 21 FTP4.3 TCP 23 TELNET4.4 TCP 25 SMTP4.5 UDP 53 DNS4.6 TCP 443 HTTPS 三、 TCP原理1. TCP头部封装格式1.1 Source Port 源端口1.2 Destination Por…...

算法:动态规划的入门理解

文章目录 算法原理题目解析第n个泰波那契数列三步问题使用最小花费爬楼梯 从本篇开始总结的是动态规划的一些内容&#xff0c;动态规划是算法中非常重要的一个版块&#xff0c;因此也是学习算法中的一个重点&#xff0c;在学习动态规划前应当要把动态规划的基础知识学习一下 算…...

最新版nacos 2.2.3服务注册与发现版本依赖问题

最新版nacos的注册服务时配置文件写的是对的&#xff0c;但就是在nacos web页面无法看见服务&#xff0c;此时你需要注意你的依赖是否正确 spring: application:name: orderservicecloud:nacos:discovery:server-addr: 122.51.115.127:8848父工程依赖&#xff1a;现在最新的s…...

2023年中国合同能源管理行业研究报告

第一章 行业概况 1.1 定义及分类 合同能源管理 (Energy Performance Contracting, EPC) 是当前能源行业中一个重要的概念&#xff0c;它构建了一个桥梁&#xff0c;将节能服务公司 (Energy Management Company, EMCo) 与用能单位紧密联系在一起。通过特定的契约形式&#xff…...

php以半小时为单位,输出指定的时间范围

//可预订小时范围$hour [];for ($i$startHour*3600;$i<$endHour*3600;$i1800){//以半小时为单位输出$startHourItem date(H:i,strtotime(date(Y-m-d))$i);//小时开始$endHourItem date(H:i,strtotime(date(Y-m-d))$i1800);//当前时间再加半小时$hourItemStr $startHourI…...

Electron应用的 asar 打包 解压

前言&#xff1a; .asar文件是一种归档文件格式&#xff0c;通常用于封装Electron应用程序的资源。Electron是一个使得开发者能够使用Web技术构建跨平台桌面应用程序的框架。为了提高性能和简化部署&#xff0c;Electron应用程序的资源通常会被打包到一个.asar文件中。 安装 as…...

蓝桥等考Python组别十七级003

第一部分:选择题 1、Python L17 (15分) 运行下面程序,输出的结果是( )。 def func(x, y): return (x + y) // 3 print(func(7, 5)) 2468正确答案:B 2、Python L17 (15</...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving

地址&#xff1a;LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂&#xff0c;正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...

基于江科大stm32屏幕驱动,实现OLED多级菜单(动画效果),结构体链表实现(独创源码)

引言 在嵌入式系统中&#xff0c;用户界面的设计往往直接影响到用户体验。本文将以STM32微控制器和OLED显示屏为例&#xff0c;介绍如何实现一个多级菜单系统。该系统支持用户通过按键导航菜单&#xff0c;执行相应操作&#xff0c;并提供平滑的滚动动画效果。 本文设计了一个…...