128. 最长连续序列

最新推荐文章于 2025-02-08 20:23:41 发布

puspos

最新推荐文章于 2025-02-08 20:23:41 发布

阅读量119

点赞数

分类专栏： hard leetcode

本文链接：https://blog.csdn.net/puspos/article/details/105301771

版权

leetcode 同时被 2 个专栏收录

235 篇文章

订阅专栏

hard

16 篇文章

订阅专栏

本文探讨了寻找最长连续子序列的有效算法。介绍了两种方法：一种是通过排序和遍历来确定连续序列长度，但时间复杂度过高；另一种是利用哈希表存储每个元素作为连续序列端点的长度，实现高效查找和更新。详细分析了哈希表方法的实现步骤，包括如何遍历数组、判断元素是否已存在于哈希表中，以及如何计算和更新连续序列的长度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

问题

在这里插入图片描述

例子

在这里插入图片描述

思路

方法1

暴力方法，先排序，再找最长的连续增长长度【每次增长1】，但是由于时间复杂度O(nlogn），超时
方法2
哈希表存储以某元素为端点的连续长度
遍历数组：
1. 元素已经存在哈希表中，跳过
2. 元素不在哈希表中，得到该元素左边的连续长度left，右边的连续长度right，则包含该元素的连续长度：len = left+right+1，更新左边端点和右边端点的连续长度，统计记录map.put(ele, len)，因为当左边或右边没有连续长度时，该元素为端点

代码

//方法1
class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length<2) return nums.length;
        //ele,以ele为端点的连续长度
        Map<Integer,Integer> map = new HashMap<>();
        
        int max = 1;
        for(int n : nums) {
            if(!map.containsKey(n)) {
                int left = map.getOrDefault(n-1, 0);
                int right = map.getOrDefault(n+1,0);
                int len = left+right+1;
                
                max = Math.max(max, len);
                map.put(n, len);
                map.put(n-left, len);
                map.put(n+right, len);
                
            }
            
        }
        
        return max;

    }
}
//方法2