【面试经典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题目来源题目解读解题思路方法一:哈希表方法二:滑动窗口 其他语言python3哈希表python3滑动窗口 写在最后 Tag 【哈希表】【滑动窗口】【数组】 题目来源 219. 存在重复元素 II 题目解读 判断在数组中有没有相同的元素小于一定的距离。 解…...
Intellij 安装配置 lombok
Intellij 安装配置 lombok 用 lombok 能够减少 setter/getter/noArgsConstructor 这样的 boilerplate 代码,所以用起来还是比较方便的。 刚开始以为直接安装到 maven 里面就能用了,运行的时候发现 Getter, Data 这些 annotation 根本找不到,…...
Chrome插件精选 — 暗色主题插件
Chrome实现同一功能的插件往往有多款产品,逐一去安装试用耗时又费力,在此为某一类型插件记录下比较好用的一款或几款,便于节省尝试的时间和精力。 Dark Reader 下载地址 (访问密码: 8276) Dark Reader是一款浏览器扩展程序,用于…...
PXE解决uefi安装centos6黑屏问题
解决pxe安装centos6黑屏 author: 铁乐与猫 date:2021.12.10 背景 主板: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对象,但是GET方法就支持? 1.1 问题背景1.2 原因分析1.3 修复方案1.3.1 修复方案一 切换使用GET方法,可以试用多个SpringQueryMap注解 (测试实际不行)1.3.2 修复方案…...
RISC-V 特权级架构
特权级别 级别的数值越大,特权级越高,掌控硬件的能力越强,在CPU硬件层面,M模式必须存在,其它模式可以不存在 执行环境调用 ecall ,这是一种很特殊的陷入类的指令, 相邻两特权级软件之间的接口正…...
目录启示:PHP 与命名空间的声明
文章目录 参考环境命名空间概念版本支持影响范围 全局命名空间概念魔术常量 \_\_NAMESPACE\_\_声明全局命名空间 声明命名空间为空间命名命名规则核心命名空间 子命名空间的声明在同一文件中定义多个命名空间无括号命名空间声明有括号命名空间声明禁止混合使用推荐使用有括号命…...
D. Divide and Equalize--Codeforces Round 903 (Div. 3)
D. Divide and Equalize 题意:让一组数中的一个数除以一个因子,一个数除以一个因子,假如经过若干次操作后能够使数组所有数相等,那么输出YES,否则输出NO。 分析:乘除因子,那么实际上就是因子的…...
保姆式教程:MAC安装Android studio(包括安装JDK,Android SDK),解决gradle下载慢的问题
文章目录 参考文章安装JDK并配置环境变量安装JDK配置JDK相关的环境变量 Android studio 安装下载Android studiogradle下载慢解决方法 安装Android SDK选择jdk版本安装SDK并配置环境变量 参考文章 原文链接 原文链接 安装JDK并配置环境变量 安装JDK 下载地址 下载后双击安装…...
Ps:选区的布尔运算
选区的布尔 Boolean运算指的是选区之间的相加(并集)、相减(差集)以及相交(交集),从而形成一个新的选区。 ◆ ◆ ◆ 使用工具选项栏 在 Ps 中,几乎所有的选区工具的工具选项栏上都有…...
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…...
破局「二次创业」:合思的新解法
在新的水温下,寻找更为良性的发展正在成为企业的必答题。对此,合思给出的不仅是一份更“省”的答题方法。也更是从认知层到行动层,最后到工具层的一张授人以渔的“渔网”。 作者|思杭 编辑|皮爷 出品|产业家 今年4月初,广州…...
第五章: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个泰波那契数列三步问题使用最小花费爬楼梯 从本篇开始总结的是动态规划的一些内容,动态规划是算法中非常重要的一个版块,因此也是学习算法中的一个重点,在学习动态规划前应当要把动态规划的基础知识学习一下 算…...
最新版nacos 2.2.3服务注册与发现版本依赖问题
最新版nacos的注册服务时配置文件写的是对的,但就是在nacos web页面无法看见服务,此时你需要注意你的依赖是否正确 spring: application:name: orderservicecloud:nacos:discovery:server-addr: 122.51.115.127:8848父工程依赖:现在最新的s…...
2023年中国合同能源管理行业研究报告
第一章 行业概况 1.1 定义及分类 合同能源管理 (Energy Performance Contracting, EPC) 是当前能源行业中一个重要的概念,它构建了一个桥梁,将节能服务公司 (Energy Management Company, EMCo) 与用能单位紧密联系在一起。通过特定的契约形式ÿ…...
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 打包 解压
前言: .asar文件是一种归档文件格式,通常用于封装Electron应用程序的资源。Electron是一个使得开发者能够使用Web技术构建跨平台桌面应用程序的框架。为了提高性能和简化部署,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</...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
