【哈希】LC 128.最长连续序列
文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接128.最长连续序列2、题目描述二、个人思路整理1、思路分析思路参考最长连续序列、两个关键优化O(n) 时间复杂度Python/Java/C/C/Go/JS/Rust、https://leetcode.cn/problems/longest-consecutive-sequence/solutions/276931/zui-chang-lian-xu-xu-lie-by-leetcode-solution/comments/2283513/此题复杂度限制在O(n)因此不能使用排序快排复杂度为O(nlogn)超出题目复杂度要求所以需要换一种思路核心就是快速判断数组中的每个元素是否可能是某一个连续序列的起点开头元素快速判断想到利用哈希表如果可能是则进行遍历查找后续递增元素是否存在若一定不是则直接跳过后续步骤进行数组中下一个元素的判断。如何进行判断数组中的元素是否可能是最长连续序列的开头元素呢先说不可能的情况当遍历到的元素值为i但数组中存在i-1那么说明当前元素就没有必要进行后续递增序列的计算因为以i-1开头的序列一定要比以i开头的序列要长不论这个以i-1开头的连续序列长度是先与以i开头的连续序列长度计算的还是迟于它最终当前以i开头计算出的连续序列的最大长度都会被更新所以这种情况没有必要再对以i开头的连续序列长度的计算排除上述不可能情况其他情况都有可能咱们需要依次计算以其他元素开头的连续序列的长度然后最终得到最大的长度。由于原数组可能存在重复元素所以我们需要去重后再进行计算以减低算法复杂度。2、解题代码classSolution{public:intlongestConsecutive(vectorintnums){unordered_setints;intmax_len0;//记录全局最大长度for(autonum:nums){s.insert(num);}for(autoi:s){if(s.count(i-1))continue;//如果i-1存在说明i不是起点跳过计算//如果找到一个起点计算以这个起点开始的序列长度inttmpi1;intcur_len1;//依次在哈希表中查找递增的元素是否存在存在则当前序列长度加一同时继续判断下一个递增元素while(s.count(tmp)){cur_len;tmp;}max_lenmax(max_len,cur_len);}returnmax_len;}};三、知识风暴空间换时间利用哈希表O(1)的查询效率代替暴力循环去匹配的过程

相关新闻

高效构建黑苹果系统:OpenCore Configurator专业配置实战指南

高效构建黑苹果系统:OpenCore Configurator专业配置实战指南

高效构建黑苹果系统:OpenCore Configurator专业配置实战指南 【免费下载链接】OpenCore-Configurator A configurator for the OpenCore Bootloader 项目地址: https://gitcode.com/gh_mirrors/op/OpenCore-Configurator 在非苹果硬件上运行macOS系统&#x…

2026/11/21 23:13:08 阅读更多 →
AI回答采集:如何从原始文本中提取品牌提及和推荐

AI回答采集:如何从原始文本中提取品牌提及和推荐

业务背景与实际约束 在AI搜索和智能问答场景中,品牌方需要了解自己的品牌在AI回答中如何被提及和推荐。然而,AI生成的文本结构多变,品牌可能以全称、简称、别名出现,推荐信号词(如“推荐”“选择”“值得考虑”&#x…

2026/11/21 9:44:14 阅读更多 →
测试方法和测试级别之间的区别

测试方法和测试级别之间的区别

测试级别 (Testing Levels) 就像是盖楼的楼层,回答了“在哪个阶段测”的问题,决定了测试的范围和对象。 测试方法 (Testing Methods) 则像是检查的工具,回答了“用什么方式测”的问题,决定了测试的视角和手段。 一个是在不同建设阶段进行的检查(级别),另一个是检查时使…

2026/11/21 6:27:01 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/20 23:27:28 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/20 23:27:28 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/20 23:27:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/20 21:55:32 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/20 23:27:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/20 22:59:12 阅读更多 →

日新闻

周新闻

月新闻