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

【面试经典150 | 哈希表】最长连续序列

文章目录

  • 写在前面
  • Tag
  • 题目来源
  • 题目解读
  • 解题思路
    • 方法一:哈希表
  • 写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……

专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:

  • Tag:介绍本题牵涉到的知识点、数据结构;
  • 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
  • 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
  • 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
  • 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【哈希表】【数组】


题目来源

128. 最长连续序列


题目解读

在无序数组中,找到最长的数字连续序列。要求时间复杂度为线性的。


解题思路

方法一:哈希表

要求的线性时间复杂度的解法,我们使用哈希集合来完成。

维护一个哈希集合,将数组中的所有元素加入到集合中;然后遍历集合中的数,统计这个数两头可以扩展到最大连续长度。

实现代码

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> hash;for (int num : nums)hash.insert(num);int ans = 0;while (!hash.empty()) {int cur = *(hash.begin());hash.erase(cur);int next = cur + 1, prev = cur - 1;while (hash.count(next))hash.erase(next++);while (hash.count(prev))hash.erase(prev--);ans = max(ans, next - prev - 1);}return ans;}
};

复杂度分析

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

空间复杂度: O ( n ) O(n) O(n),哈希集合占用了额外的


写在最后

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

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

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

相关文章:

【面试经典150 | 哈希表】最长连续序列

文章目录 写在前面Tag题目来源题目解读解题思路方法一&#xff1a;哈希表 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法&#xff0c;两到三天更新一篇文章&#xff0c;欢迎催更…… 专栏内容以分析题目为主&#xff0c;并附带一些对于本题涉及到的数据结构等内…...

如何构建安全的App网络通信?

前言 说到安全肯定逃不开数据的加解密&#xff0c;数据本地存储大多用对称加解密来实现&#xff0c;那网络传输数据的时候是不是也用对称加解密来实现&#xff1f;没错&#xff0c;常规网络通信时&#xff0c;大部分网络传输过程中基本也是用对称加解密来实现的&#xff0c;毕竟…...

Chrome插件精选 — 网页截图插件

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

react+antd封装表格组件2.0

reactantd封装表格组件2.0 1.0版本 仅仅封装组件&#xff0c;不涉及方法需要掌握知识点useImperativeHandle 组件代码引用 1.0版本 仅仅封装组件&#xff0c;不涉及方法 1.0 仅封装组件 此方法把所用方法集体封装&#xff0c;以后就可以无脑开发拉&#xff01; 只需传入路径&…...

互联网Java工程师面试题·Java 并发编程篇·第八弹

目录 33、Java 死锁以及如何避免&#xff1f; 34、死锁的原因 35、怎么唤醒一个阻塞的线程 36、不可变对象对多线程有什么帮助 37、什么是多线程的上下文切换 38、如果你提交任务时&#xff0c;线程池队列已满&#xff0c;这时会发生什么这里区分一下&#xff1a; 39、J…...

21面向对象描述器

目录 1、什么是描述器&#xff1f; 1、原始的代码可以理解成为这样&#xff1a; 2、增加解释器可以改成如下&#xff0c;解释器就是集增删改查为一体的一个小的property 有一点需要注意的地方是&#xff1a;property里面内置的参数不是get_age()就是不用调用。 3、装饰器可…...

高校教务系统登录页面JS分析——皖西学院

高校教务系统密码加密逻辑及JS逆向 本文将介绍皖西学院教务系统的密码加密逻辑以及使用JavaScript进行逆向分析的过程。通过本文&#xff0c;你将了解到密码加密的基本概念、常用加密算法以及如何通过逆向分析来破解密码。 本文仅供交流学习&#xff0c;勿用于非法用途。 一、密…...

单片机综合小项目

一、单片机做项目常识 1.行业常识 2.方案选型 3.此项目定位和思路 二、单片机的小项目介绍 1.项目名称&#xff1a;基于51单片机的温度报警器 &#xff08;1&#xff09;主控&#xff1a;stc51&#xff1b; &#xff08;2&#xff09;编程语言&#xff1a;C语言 &#xff08;…...

docker下的onlyoffice安装(for seafile)

docker镜像拉取 # 拉取 onlyoffice 镜像docker pull onlyoffice/documentserver 创建所需目录 # 创建几个目录 用于 onlyoffice 的数据卷cd /opt# 建议与 seafile 容器都放在 /opt 目录方便管理mkdir seafile-onlyofficecd seafile-onlyofficemkdir logmkdir datamkdir libmkd…...

1 两数之和

解题思路&#xff1a; \qquad 对每个数nums[i]&#xff0c;仅需在数组中搜索target-nums[i]是否存在。 优化思路&#xff1a; \qquad 首先能想到&#xff0c;利用哈希表O(1)查询target-nums[i]。 \qquad 建立map<int, vector<int>>的表能够处理重复元素&#x…...

NewStarCTF2023week2-Unserialize?

代码审计&#xff1a; 定义了一个eval类&#xff0c;该类下有一个私有变量cmd和公有成员函数destruct()&#xff0c;该函数在对象的所有引用都被删除或类被销毁时会自动调用&#xff1b; 调用该函数则会执行一个正则表达式进行正则匹配&#xff0c;过滤掉了一些常用命令和bas…...

OpenMesh 最优选点策略

文章目录 一、简介二、实现代码三、实现效果参考文献一、简介 继续沿着之前的思路:OpenMesh 网格顶点Quadric误差计算,有时候,无论是网格简化或是网格平滑,总会涉及到添加一个新的顶点的问题,那么新顶点应该怎么生成呢?以网格的简化操作为例,假设我们要合并两个顶点,也…...

服务器内存总量和内存条有差异是什么问题 103.239.244.X

服务器内存总量和内存条上标注的容量可能会存在一些差异&#xff0c;这是由于以下几个原因&#xff1a; 部分内存被保留给系统和其他硬件设备&#xff1a;在服务器中&#xff0c;一部分内存可能被保留给系统和其他硬件设备&#xff0c;比如显卡、网卡、RAID卡等。这些设备需要一…...

WPF DataGrid详细列表手动显示与隐藏

设置显示序号与折叠显示样式 <DataTemplate x:Key"dtNum"><Button BorderBrush"Transparent" Style"{x:Null}" Click"BtnRowDetail_ShowHideClick" FontSize"16" Background"Transparent"><Stack…...

Compose 组件 - 分页器 HorizontalPager、VerticalPager

一、概念 类似于 ViewPager&#xff0c;1.4 版本之前需要借助 accompanis 库&#xff0c;底层基于 LazyColumn、LazyRow 实现&#xff0c;在使用上也基本相同。默认情况下 HorizontalPager 占据屏幕的整个宽度&#xff0c;VerticalPager 会占据整个高度。 fun HorizontalPager(…...

Web3 招聘 | Bitget、MyShell、imToken、Arweave 多项目招聘中

「Web3 招聘」是 TinTinLand 为 Web3 项目和求职者创建的一个招聘信息汇集专栏。本栏目将持续更新区块链行业招聘信息&#xff0c;满足不同求职者与项目方的多样需求。欢迎各项目方联系 TinTinLand 发布职位需求&#xff0c;欢迎求职者关注 TinTinLand 获取最新招聘信息。 此外…...

通过HTTP发送大量数据的三种方法

在网络的早期时期&#xff0c;人们发送的文件大小仅为几KB。到了2023年&#xff0c;我们享受着高分辨率的MB级别图像&#xff0c;并在几GB的4K&#xff08;即将是8K&#xff09;视频中观看。 即使有良好的互联网连接&#xff0c;下载一个5GB的文件仍然需要一些时间。如果你拥有…...

【MySQL】索引和事物

目录 ♫索引 ♪什么是索引 ♪索引的数据结构 ♪索引的使用 ♫事务 ♪什么是事务 ♪事务的特性 ♪事务的使用 ♫索引 ♪什么是索引 索引是存储在磁盘上的一个数据结构&#xff0c;通过索引可以快速地定位到存储在磁盘上的数据。 索引在提高查询速度的同时&#xff0c;还提…...

win11下的VS2022+QT6+VTK9.2+PCL1.13.1联合开发环境配置及踩坑记录

准备工作&#xff1a; 安装VS2022&#xff1a;这个比较简单&#xff0c;网上随便找个教程就行 安装QT并为VS2022添加QT Creater插件&#xff1a;VS2022配置Qt6_vs2022 qt6-CSDN博客 安装PCL&#xff1a;vs2022配置pcl1.13.1_pcl配置-CSDN博客 安装PCL过程中本身也会安装VTK&…...

CEdit

1、https://www.cnblogs.com/milanleon/p/5626174.html 2、CEdit控件提供访问函数主要有&#xff1a; int GetWindowText(LPCTSTR lpszStringBuf,intnMaxCount) 获取控件文本&#xff0c;与ReadText()功能相同 void SetWindowText(LPCTSTR lpszString) 设置控件文本 void …...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !

我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...

热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁

赛门铁克威胁猎手团队最新报告披露&#xff0c;数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据&#xff0c;严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能&#xff0c;但SEMR…...