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

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

Chrome插件精选 — 网页截图插件
Chrome实现同一功能的插件往往有多款产品,逐一去安装试用耗时又费力,在此为某一类型插件记录下比较好用的一款或几款,便于节省尝试的时间和精力。 捕捉网页截图 - FireShot 下载地址 (访问密码: 8276) Fireshot是一款浏览器插件,…...
react+antd封装表格组件2.0
reactantd封装表格组件2.0 1.0版本 仅仅封装组件,不涉及方法需要掌握知识点useImperativeHandle 组件代码引用 1.0版本 仅仅封装组件,不涉及方法 1.0 仅封装组件 此方法把所用方法集体封装,以后就可以无脑开发拉! 只需传入路径&…...

互联网Java工程师面试题·Java 并发编程篇·第八弹
目录 33、Java 死锁以及如何避免? 34、死锁的原因 35、怎么唤醒一个阻塞的线程 36、不可变对象对多线程有什么帮助 37、什么是多线程的上下文切换 38、如果你提交任务时,线程池队列已满,这时会发生什么这里区分一下: 39、J…...

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

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

单片机综合小项目
一、单片机做项目常识 1.行业常识 2.方案选型 3.此项目定位和思路 二、单片机的小项目介绍 1.项目名称:基于51单片机的温度报警器 (1)主控:stc51; (2)编程语言:C语言 (…...
docker下的onlyoffice安装(for seafile)
docker镜像拉取 # 拉取 onlyoffice 镜像docker pull onlyoffice/documentserver 创建所需目录 # 创建几个目录 用于 onlyoffice 的数据卷cd /opt# 建议与 seafile 容器都放在 /opt 目录方便管理mkdir seafile-onlyofficecd seafile-onlyofficemkdir logmkdir datamkdir libmkd…...

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

NewStarCTF2023week2-Unserialize?
代码审计: 定义了一个eval类,该类下有一个私有变量cmd和公有成员函数destruct(),该函数在对象的所有引用都被删除或类被销毁时会自动调用; 调用该函数则会执行一个正则表达式进行正则匹配,过滤掉了一些常用命令和bas…...
OpenMesh 最优选点策略
文章目录 一、简介二、实现代码三、实现效果参考文献一、简介 继续沿着之前的思路:OpenMesh 网格顶点Quadric误差计算,有时候,无论是网格简化或是网格平滑,总会涉及到添加一个新的顶点的问题,那么新顶点应该怎么生成呢?以网格的简化操作为例,假设我们要合并两个顶点,也…...
服务器内存总量和内存条有差异是什么问题 103.239.244.X
服务器内存总量和内存条上标注的容量可能会存在一些差异,这是由于以下几个原因: 部分内存被保留给系统和其他硬件设备:在服务器中,一部分内存可能被保留给系统和其他硬件设备,比如显卡、网卡、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,1.4 版本之前需要借助 accompanis 库,底层基于 LazyColumn、LazyRow 实现,在使用上也基本相同。默认情况下 HorizontalPager 占据屏幕的整个宽度,VerticalPager 会占据整个高度。 fun HorizontalPager(…...

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

通过HTTP发送大量数据的三种方法
在网络的早期时期,人们发送的文件大小仅为几KB。到了2023年,我们享受着高分辨率的MB级别图像,并在几GB的4K(即将是8K)视频中观看。 即使有良好的互联网连接,下载一个5GB的文件仍然需要一些时间。如果你拥有…...
【MySQL】索引和事物
目录 ♫索引 ♪什么是索引 ♪索引的数据结构 ♪索引的使用 ♫事务 ♪什么是事务 ♪事务的特性 ♪事务的使用 ♫索引 ♪什么是索引 索引是存储在磁盘上的一个数据结构,通过索引可以快速地定位到存储在磁盘上的数据。 索引在提高查询速度的同时,还提…...

win11下的VS2022+QT6+VTK9.2+PCL1.13.1联合开发环境配置及踩坑记录
准备工作: 安装VS2022:这个比较简单,网上随便找个教程就行 安装QT并为VS2022添加QT Creater插件:VS2022配置Qt6_vs2022 qt6-CSDN博客 安装PCL:vs2022配置pcl1.13.1_pcl配置-CSDN博客 安装PCL过程中本身也会安装VTK&…...
CEdit
1、https://www.cnblogs.com/milanleon/p/5626174.html 2、CEdit控件提供访问函数主要有: int GetWindowText(LPCTSTR lpszStringBuf,intnMaxCount) 获取控件文本,与ReadText()功能相同 void SetWindowText(LPCTSTR lpszString) 设置控件文本 void …...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...

高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...

优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...

Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...

基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程
STM32F1 本教程使用零知标准板(STM32F103RBT6)通过I2C驱动ICM20948九轴传感器,实现姿态解算,并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化,适合嵌入式及物联网开发者。在基础驱动上新增…...

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