【面试经典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 …...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...

使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
LRU 缓存机制详解与实现(Java版) + 力扣解决
📌 LRU 缓存机制详解与实现(Java版) 一、📖 问题背景 在日常开发中,我们经常会使用 缓存(Cache) 来提升性能。但由于内存有限,缓存不可能无限增长,于是需要策略决定&am…...