当前位置：首页 > article >正文

算法题解记录32+++最长连续序列（百题筑基）

article 2025/1/18 18:05:08

你们好，我是蚊子码农，好久不见。由于秋招求职的繁琐事情，我有很长一段时间没更新博客，希望我的粉丝们能够谅解。
秋招我拿到了一些offer，最终决定去一个主要做“网络安全”业务的公司工作，也许明天会更好？也许明天会更糟？我不知道，但是未来曲折难行、旅途永无止境，希望我能学到更多知识、做出更多成果物，甚至在这个领域，闯出一点名声吧。
说回原题，我决定把欠下的“百题筑基”（原名百日筑基）做完，这应该是我这段时间最想做的东西了。
另外，在过去3年的学习生涯里，我有一些编程项目，我觉得很有意思，也许会发布在csdn上，当然，我也想开辟一个douyin账号，在里面积累一些粉丝什么的。
不知道有没有公司招收实习生？
我是985工科出生，有丰富的基础知识和实践经验，不妨看看我？
说回主题，下面我讲解一下这道题目吧。

核心概念：开头数【我自创的】
【开头数：一个连续序列的第一个数，比如（1，2）即1是开头数，2不是开头数；（7，8，9，10，11）即7为开头数，其它不是】

一、题目描述

题目难度：中等

1.题目

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

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

2.示例

示例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

3.其它约束

第一，0 <= nums.length <= 10^5

第二，-10^9 <= nums[i] <= 10^9

二、解题准备（朴素方案）

本题要求从数组中，拿到一个最长连续序列。
对于无序数组，简单的排序后，就可以很轻松地拿下本题。
需要关注的两个异常是

第一，最长连续序列的头部，不一定从最小的数开始

比如数组【1，2，7，8，9，10，11】
最长序列为【7，8，9，10，11】，答案是5。
如果我们贸然从头计算，那么，就会出错。
解决方案很简单，有两个。
第一，我们可以对有序数组中，每个数进行一次遍历，判断以每个数开头的连续序列的长度。【当然，明显时间复杂度很高】
第二，我们每次遍历前，判断一下这个数是否是开头数【开头数：一个连续序列的第一个数，比如（1，2）即1是开头数，2不是开头数；（7，8，9，10，11）即7为开头数，其它不是】
这样子，能够省去很多时间。

第二，在一个数组中，可能存在同值。

比如数组【1，2，2，2，3，3，3】
这个最长序列的长度其实只有3，但需要格外处理。
假如我们用 if( data【i】 = data【i-1】 + 1 )，就得再加一层
if（ data【i】 = data【i-1】）。
此时，才能正确判断。

三、朴素方案的问题

第一，时间复杂度过高

对一个数组进行排序，时间复杂度最快也超过 O（N logN），这就代表着不能满足题意。

第二，代码逻辑比较复杂

虽然编程时，代码逻辑复杂不是大问题（甚至很多复杂问题，必须要复杂逻辑才能解决），当然，就本题来看，我们只需要得到一个最长连续序列的值，却需要2个大系统
第一个，是排序算法。【可以调用函数】
第二个，是计数系统。
在计数系统中，需要从头到尾遍历所有值。
此时，需要

第一，判断数是否序列的开头数。

第二，如果是开头数，从头到尾遍历一次。
【在这个遍历中，需要剔除重复数据的影响，比如 1，1，2，3，4，4】

代码逻辑非常复杂，假如是面试手撕算法，大概率没法过关。

这也是我的一点经验，在编程前，最好提前对可能的算法解决方案，进行一次评估，如果编程时间过长，最好还是寻找优化方案，或者干脆另找新思路。

四、解决方案

1.思考

我们知道，原数组排序，时间复杂度太高，不可能解决本题。
那么，不排序，有什么方法解决？
如果每次拿到一个数，然后用这个数，在数组里寻找下一个数，并判断，这是猴子行为，时间复杂度不说，单单判断终止条件，就非常麻烦。
比如【1，3，2，4】，先拿到1，然后在原数组找2，拿到2，找3，拿到3，找4。【每一次，都需要重新判断，时间复杂度应该是O（N！）

有丰富编程经验的我们，立马就知道了

O（N）的算法，在原有数据结构的限制下，几乎不可能完成。【排序也不能排，随机读取也读不了】

2.什么数据结构，可以扛起大旗？

我们需要一个结构，插入、读取时间复杂度为O（1），并且最好有序。
但凡，插入时间复杂度是O（LogN），那么插入n个元素，总体时间复杂度已经是O（N logN）了，不满足题意。
明显，就是哈希表。
当然，由于我们想要剔除重复元素，并且key、Value两个域中，有一个域用不到，所以我们选择Java的HashSet。
HashSet，基于哈希表实现，能够完成哈希表的任务。

3.哈希集合无序性

集合是无序的，但是，题目要求的元素之间的关系，赋予了它们相关性。
比如，我们得到一个开头数为1，我们想找到2。
在哈希集合中，直接就能得到。

这就相当于

哈希集合已经 有序了

4.算法思路

我们使用朴素方案中，基于排序数组的算法。
此时，由于集合自动去重，所以我们只需要面对一个问题。

第一，最长序列的开头数，不能确定

假如我们先对集合中每个数遍历，然后再次遍历，时间复杂度最差为O（N）
比如集合（1，2，3，4，5）
先对1遍历，1，2，3，4，5
对2遍历，2，3，4，5
对3遍历，3，4，5
对4遍历，4，5
对5遍历，5
可以看到，每个数都可能遍历N次，再加上外层循环【即遍历哈希集合的循环】
总体时间复杂度为O（N * N）

第二，解决方案

对哈希集合遍历，是不可避免的。
但有了数组的思路，我们其实可以知道。
假如一个数不是开头数，我们完全可以跳过。（因为，序列【2，3，4】不可能比【1，2，3，4】更长）
因此，直接跳过即可。

第三，解决方案复杂度O（1）证明

对于开头数，我们只遍历1次，所以其时间复杂度为O（1）
有些人问，对于数组【1，3，5，7，9】
外层循环遍历后，内层也每次都要遍历，时间复杂度怎么会O（1）呢？
外层O（N）遍历后，内层对于开头数，会遍历1次。
也就是说，开头数至多遍历N次。
其他数，只判断后，即结束，仅1次。
所以，内层 * 外层，共O（N）。

五、代码

class Solution {
    public int longestConsecutive(int[] nums) {
        int count = 0;
       
        // 存储数据
        Set<Integer> data = new HashSet<>();

        // 存储
        for(int i:nums){
            data.add(i);
        }

        // 从i开始，遍历count
        for(int i:data){
            int temp = i-1;
            int gm = 0;

            if(!data.contains(temp)){
                temp++;
                while(data.contains(temp)){
                    gm++;
                    temp++;
                }

                count = Math.max(gm, count);
            }
            // 如果存在，那么说明非开始
        }

        return count;
    }
}