☆打卡算法☆LeetCode 128. 最长连续序列 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个未排序的整数数组，找出数字连续的最长序列的长度。”

题目链接：

来源：力扣（LeetCode）

链接： 128. 最长连续序列 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给定一个未排序的整数数组 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

二、解题

1、思路分析

本题可以枚举出所有数字，然后匹配地找出数字连续的最长连续序列。

最长连续序列必然有这样的规律：x,x+1,x+2,…,x+n，长度为n。

但是这样会导致算法时间复杂度到达O(n²)，也就是一层枚举，一层匹配，无法满足题目要求。

可以使用哈希表存储数组中的数，这样查看一个数就可以达到O(1)的时间复杂度。

2、代码实现

代码参考：

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}

3、时间复杂度

时间复杂度：O(n)

其中n为数组的长度。

空间复杂度：O(n)

哈希表存储数组中所有的数需要O(n)的空间。

三、总结

在代码中，需要先找到最长连续序列的第一个数x，这个可以判断哈希表中是否存在一个x-1的数。

如果存在就说明x-1为第一个数，那么就接着判断；如果不存在就可以进入内层循环。

也就是只有一个数是连续序列的第一个数的情况下才会进行内层循环，然后在内层循环中匹配连续序列中的数。