128. 最长连续序列

简介: 128. 最长连续序列

最长连续序列

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

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

示例 1:

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/longest-consecutive-sequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

两个哈希表
连续区间头表+连续区间尾表

image.png
100来到的过程
头表加入(100,1),1为长度
尾表加入(100,1)

image.png
加入3
image.png
加入4,查看有没有能连接的区间
image.png
查看头表,发现3,将3与4连起来,变成(3,2),代表从3出发,可以连成2个长度的区间
查看尾表,发现3,将3与4连起来,变成(4,2),代表以4为结尾,可以连成2个长度的区间

每个数来的时候都自己建出自己的区间,看看跟之前都不能合,看看后面能不能合,
你每次都严严格格的合完之后,你问我最后有多长的连续区间,你随便找-张表,把value最大值拿出来
每一个数来到的时候,对于哈希表的操作都是0(1)

代码

两个哈希表的版本

    public static int longestConsecutive2(int[] nums) {
        HashMap<Integer, Integer> headMap = new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> tailMap = new HashMap<Integer, Integer>();
        HashSet<Integer> visited = new HashSet<>();
        for (int num : nums) {
            if (!visited.contains(num)) {
                visited.add(num);
                headMap.put(num, 1);
                tailMap.put(num, 1);
                if (tailMap.containsKey(num - 1)) {
                    int preLen = tailMap.get(num - 1);
                    int preHead = num - preLen;
                    headMap.put(preHead, preLen + 1);
                    tailMap.put(num, preLen + 1);
                    headMap.remove(num);
                    tailMap.remove(num - 1);
                }
                if (headMap.containsKey(num + 1)) {
                    int preLen = tailMap.get(num);
                    int preHead = num - preLen + 1;
                    int postLen = headMap.get(num + 1);
                    int postTail = num + postLen;
                    headMap.put(preHead, preLen + postLen);
                    tailMap.put(postTail, preLen + postLen);
                    headMap.remove(num + 1);
                    tailMap.remove(num);
                }
            }
        }
        int ans = 0;
        for (int len : headMap.values()) {
            ans = Math.max(ans, len);
        }
        return ans;
    }

一个哈希表

    public static int longestConsecutive(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int len = 0;
        for (int num : nums) {
            if (!map.containsKey(num)) {
                map.put(num, 1);
                int preLen = map.containsKey(num - 1) ? map.get(num - 1) : 0;
                int posLen = map.containsKey(num + 1) ? map.get(num + 1) : 0;
                int all = preLen + posLen + 1;
                map.put(num - preLen, all);
                map.put(num + posLen, all);
                len = Math.max(len, all);
            }
        }
        return len;
    }
相关文章
|
10月前
【报错】:Module path has been externalized for browser...
【报错】:Module path has been externalized for browser...
839 0
|
缓存 Dubbo 应用服务中间件
Dubbo + Nacos这么玩就失去高可用的能力了
酱香配拿铁喝了伤头,Dubbo配Nacos这么玩也会伤头。本文介绍Dubbo配合Nacos搭建的微服务系统,在Nacos-Server集群重启时出现的问题。过程中通过种种现象、猜测、翻看源码、实践,最终让Nacos-Server平滑重启。
|
存储 SQL 分布式计算
clickhouse集群安装与实践
因项目需要,将阿里云中间件tablestore替换成clickhouse,并将tablestore中的亿级数据迁移到clickhouse
1289 2
|
10月前
|
设计模式 Java 编译器
面向对象编程中的继承与多态:深入理解父类引用指向子类实例
面向对象编程中的继承与多态:深入理解父类引用指向子类实例
|
XML JSON 负载均衡
微服务:通信协议:Restful,RPC(Dubbo、Motan、gRPC)
微服务:通信协议:Restful,RPC(Dubbo、Motan、gRPC)
1715 1
微服务:通信协议:Restful,RPC(Dubbo、Motan、gRPC)
|
10月前
|
SpringCloudAlibaba 负载均衡 Java
【一】SpringCloud Alibaba之Nacos整合篇(作为注册中心)
【一】SpringCloud Alibaba之Nacos整合篇(作为注册中心)
452 1
【一】SpringCloud Alibaba之Nacos整合篇(作为注册中心)
|
10月前
|
SpringCloudAlibaba Dubbo 前端开发
【三】SpringCloud Alibaba之Nacos整合篇(作为配置中心)
【三】SpringCloud Alibaba之Nacos整合篇(作为配置中心)
616 0
|
算法 Java Sentinel
限流算法(计数器、滑动时间窗口、漏斗、令牌)原理以及代码实现
> 本文会对这4个限流算法进行详细说明,并输出实现限流算法的代码示例。 > 代码是按照自己的理解写的,很简单的实现了功能,还请大佬们多多交流找bug。
826 0
|
10月前
|
SpringCloudAlibaba 负载均衡 Java
【二】SpringCloud Alibaba之Nacos整合篇(配置负载均衡)
【二】SpringCloud Alibaba之Nacos整合篇(配置负载均衡)
1281 0
|
XML JSON 算法
JWT详细讲解(保姆级教程)
本篇博文详细讲解JWT概念,组成,运行过程,和SAM相比的优势,并附加SpringBoot整合JWT的案例。
JWT详细讲解(保姆级教程)