当前位置: 首页 > 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 …...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

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

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...