当前位置: 首页 > news >正文

LeetCode哈希表:最长连续序列

LeetCode哈希表:最长连续序列

题目描述

给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4

示例 2:

输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9

解题思路

首先想到的方法就是先排序,然后再找到符合条件序列,但这样的话复杂度就不符合题目要求。最好的排序的是nlogn因此排序这条路走不通,考虑采用哈希,哈希的一个优点就是寻找元素容易,那就考虑怎么去找这个元素,两种方案,

  • 第一种:找到一个序列最小值再以此向大的进行判断
  • 第二种:找到一个序列最大的向小的方向判断

最后再返回最长长度

步骤如下:
  1. 创建HashSet:首先,创建一个HashSet,用于存储数组中的元素。HashSet的目的是为了快速检查数组中是否包含某个元素,以及在O(1)时间内添加元素。
  2. 将数组元素加入HashSet:遍历输入数组nums,将每个元素加入HashSet
  3. 寻找连续序列:对于每个元素num,检查是否存在num - 1,如果不存在,说明num可能是一个连续序列的起点。然后,从num开始,通过不断检查num + 1是否在HashSet中,来找到连续序列的长度。
  4. 更新最长连续序列的长度:在每次找到一个连续序列后,更新最长连续序列的长度。
  5. 返回结果:返回最终找到的最长连续序列的长度。

代码

public class hash2 {public int longestConsecutive(int[] nums) {HashSet<Integer> set=new HashSet<>();for (int num : nums) {set.add(num);}int ans=0;for (int num : set) {int right=num;if (!set.contains(right - 1)) {while (set.contains(right+1))right++;}ans=Math.max(ans,right-num+1);}return ans;}public static void main(String[] args) {hash2 ha=new hash2();System.out.println(ha.longestConsecutive(new int[]{100, 4, 200, 1, 3, 2}));}
}

优化以及其他思想的方法

  • 方法1 哈希集合(最普遍也最简单的思路,必须掌握)
  • 方法2 哈希表(思路1的进阶)
  • 方法3 动态规划(极其巧妙,推荐掌握)
  • 方法4 并查集(建议掌握)

传送:迪迦~~

相关文章:

LeetCode哈希表:最长连续序列

LeetCode哈希表&#xff1a;最长连续序列 题目描述 给定一个未排序的整数数组 nums &#xff0c;找出数字连续的最长序列&#xff08;不要求序列元素在原数组中连续&#xff09;的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1&#xff1a; 输入&…...

SpringBoot+redis实现接口防刷

写一个RedisService&#xff0c;实现获取Redis 的set、get、incr&#xff08;相当于计数器&#xff09; 写inferface注解类 做一个拦截器&#xff0c;因为要先于控制器判断 将拦截器注入Springboot 文章目录 目录 文章目录 前言 一、引入依赖 二、使用步骤 2.1 RedisServic…...

5G承载网和大客户承载的演进

文章目录 移动4/5G承载网联通和电信4/5G承载网M-OTN&#xff08;Metro-optimized OTN&#xff09;&#xff0c;城域型光传送网PeOTN&#xff08;packet enhanced optical transport network&#xff09;&#xff0c;分组增强型OTN板卡增强型PeOTN集中交叉型PeOTN VC-OTN&#x…...

智慧工地一体化解决方案(里程碑管理)源码

智慧工地为管理人员提供及时、高效、优质的远程管理服务&#xff0c;提升安全管理水平&#xff0c;确保施工安全提高施工质量。实现对人、机、料、法、环的全方位实时监控&#xff0c;变被动“监督”为主动“监控”。 一、建设背景 施工现场有数量多、分布广&#xff0c;总部统…...

熬夜会秃头——beta冲刺Day2

这个作业属于哪个课程2301-计算机学院-软件工程社区-CSDN社区云这个作业要求在哪里团队作业—beta冲刺事后诸葛亮-CSDN社区这个作业的目标记录beta冲刺Day2团队名称熬夜会秃头团队置顶集合随笔链接熬夜会秃头——Beta冲刺置顶随笔-CSDN社区 目录 一、团队成员会议总结 1、成员…...

【linux】信号——信号保存+信号处理

信号保存信号处理 1.信号保存1.1信号其他相关概念1.2信号在内核中的表示 2.信号处理2.1信号的捕捉流程2.2sigset_t2.3信号集操作函数2.4实操2.5捕捉信号的方法 3.可重入函数4.volatile5.SIGCHLD信号 自我名言&#xff1a;只有努力&#xff0c;才能追逐梦想&#xff0c;只有努力…...

雷军:我的程序人生路

今天有朋友发给我一篇我在20年前在BBS上写的帖子。那还是1996年&#xff0c;我们通过电话线拨号连接到西点BBS上飙帖子玩的年代。那是一个互联网混沌初开的年代&#xff0c;那是一个BBS和Email几乎主宰了全部互联网的年代&#xff0c;那是一个青春的理想和热血沸腾的年代。 我…...

Linux 磁盘分区处理

最近实施过程中遇到客户提供给我们的服务器操作系统和Docke容器环境都已经安装完成&#xff0c;但磁盘的分区没有进行整理好。磁盘总共270G&#xff0c;系统安装分配了60G&#xff0c;剩余未创建分配需要处理。由于分区情况每家不一样&#xff0c;但大致流程都是相同的&#xf…...

利用ogr2ogr从PostGIS中导出/导入Tab/Dxf/Geojson等格式数据

ogr2ogr Demo Command 先查看下当前gdal支持的全部格式&#xff0c;部分gdal版本可能不支持PostGIS。 如出现PostgreSQL表名支持。 #全部支持的格式 ogrinfo --formats | sort #AVCBin -vector- (rov): Arc/Info Binary Coverage #AVCE00 -vector- (rov): Arc/Info E00 (ASC…...

【深度优先】LeetCode1932:合并多棵二叉搜索树

作者推荐 动态规划LeetCode2552&#xff1a;优化了6版的1324模式 题目 给你 n 个 二叉搜索树的根节点 &#xff0c;存储在数组 trees 中&#xff08;下标从 0 开始&#xff09;&#xff0c;对应 n 棵不同的二叉搜索树。trees 中的每棵二叉搜索树 最多有 3 个节点 &#xff0…...

monorepo多项目管理主流实现方式:1.learn + yarn/npm workspace 2.pnpm

npm域级包 随着npm包越来越多&#xff0c;而且包名也只能是唯一的&#xff0c;如果一个名字被别人占了&#xff0c;那你就不能再使用这个名字&#xff1b;假设我想要开发一个utils包&#xff0c;但是张三已经发布了一个utils包&#xff0c;那我的包名就不能叫utils了&#xff…...

【斗罗二】暗杀霍雨浩行动,马小桃霸气回击,江楠楠首秀武魂兔兔

Hello,小伙伴们&#xff0c;我是拾荒君。 《斗罗大陆Ⅱ绝世唐门》第25集更新了&#xff01;和小伙伴们一样&#xff0c;一更新&#xff0c;拾荒君就急不可待地观看这一集。故事情节高潮迭起&#xff0c;尤其是霍雨浩与王冬面对六名杀手的惊险场景&#xff0c;真是让人心跳加速…...

[ 蓝桥杯Web真题 ]-年度明星项目

目录 引入 介绍 准备 目标 效果 规定 思路 知识补充 解答参考 引入 hello&#xff0c;大家好&#xff01;我注意到了之前发的一篇蓝桥杯Web应用开发的文章是关注度最高的&#xff0c;可能大部分关注我的小伙伴对蓝桥杯Web应用开发比较感兴趣&#xff0c;或者想要参加…...

Maven终端打包时报Unknown lifecycle phase “.test.skip=true“

错误实例代码 mvn clean package -Dmaven.test.skiptrue 再windows的cmd窗口进行项目打包&#xff0c;需要将参数用英文符号包裹起来“ ” 【正确的实例】&#xff1a;mvn clean package ’-Dmaven.test.skiptrue‘ PS D:\BaiduNetdiskDownload\qian\Springboot-Vue\bi…...

Linux MIPI 调试中常见的问题

一、概述 做嵌入式工作的小伙伴知道&#xff0c;有时候程序编写没有调试过程中费时&#xff0c;之间笔记里有 MIPI 摄像头驱动开发的过程&#xff0c;有需要的小伙伴可以参考&#xff1a;Linux RN6752 驱动编写。而我也是第一次琢磨 MIPI 协议&#xff0c;其中有很多不明白的地…...

使用极限网关助力 ES 集群无缝升级、迁移上/下云

在工作中大家可能会遇到以下这些场景&#xff1a; 自建 ES 集群需要平滑迁移到 XX 云&#xff1b;从 XX 云将 ES 集群迁移到自建机房&#xff1b;ES 集群进行跨版本升级&#xff0c;同时保留回退能力&#xff1b; 这些场景往往都还有个共同的需求&#xff1a;迁移过程要保证业…...

RedisTemplate的配置和讲解以及和StringRedisTemplate的区别

本文主要讲redisTempalte的几种常用的序列化方式 string&#xff0c;我们大部分情况下都希望存入redis的数据可读性强一些&#xff0c;并且value也不总是一个规则的类型&#xff0c;所以这里也是不用json序列化的原因&#xff0c;可以更自由方便&#xff0c;下边提供配置方法 …...

在oracle中的scn技术

SCN可以说是Oracle中一个很基础的部分&#xff0c;但同时它也是一个很重要的。它是系统中维持数据的一致性和顺序恢复的重要标志&#xff0c;是数据库非常重要的一种数据结构。 转载&#xff1a;深入剖析 - Oracle SCN机制详细解读 - 知乎 (zhihu.com)https://zhuanlan.zhihu.…...

LINUX 嵌入式C编程--信号编程

基本概念 信号是事件发生时对进程的通知机制&#xff0c;也可以把它称为软件中断。信号与硬件中断的相似之处在于能够打断程序当前执行的正常流程&#xff0c;其实是在软件层次上对中断机制的一种模拟。信号提供了一种处理异步事件的方法。 信号目的 **信号的目的是用来通信…...

Linux:优化原则

web系统的优化原则&#xff1a; 从单机到集群 对Linux系统自身的优化原则&#xff1a;...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...