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

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

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

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving

地址&#xff1a;LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂&#xff0c;正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...