Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

前言

力扣第128题 最长连续序列 如下所示：

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

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

示例 1：

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

一、思路

题目比较简单，也很好理解。一个比较朴素的思路就是两次遍历：先遍历一遍数组，让其从小到大排序。然后再遍历一次数组，找出最大的连续长度。

我刚开始就是使用两次遍历这种方式的，提交代码后发现无法通过所有的测试用例。在排序数组的的时候，需要将重复的元素剔除掉。不然会导致计算最长连续长度的时候不准确。

后面我注意到要使用时间复杂度为 O(N) 的算法，那怎么保证时间复杂度为 O(N) 呢？

我们直到哈希表可以有效的避免因为遍历数组而增加的时间复杂度，所以我们这里可以使用 HashSet 来存储数组中的元素。（当然也可以使用 HashMap，key存值，value存 null 即可）。

实现的大致思路如下所示：

遍历数组，将数组的元素存入哈希表
为避免遍历整个数组，我们可以只选取比当前元素大 1 的元素进行统计。即当当前的值的前一位在哈希表中时，可直接跳过
返回最大的连续长度

举个例子

此处以示例中的 nums = [100,4,200,1,3,2] 作为例子

将数组放入哈希表
遍历哈希表，第一个取到的元素为 1。此时 0 不在哈希表中，故一直向后寻找，直至 4，此时更新结果为 4。
哈希表取第二个元素 2，此时 1 在哈希表中，故跳过。同理会跳过 3 和 4
至于 100 和 200 的最长长度为 1
返回结果 4

二、实现

实现代码

实现代码与思路中保持一致

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }
    int ret = 0;

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

            while (set.contains(currentNum + 1)) {
                currentNum += 1;
                currentRet += 1;
            }

            ret = Math.max(ret, currentRet);
        }
    }

    return ret;
}
复制代码

测试代码

public static void main(String[] args) {
    int[] nums = {100,4,200,1,3,2};
    int[] nums1 = {9,1,4,7,3,-1,0,5,8,-1,6};
    int[] nums2 = {1,2,0,1};
    new Number128().longestConsecutive(nums);
}
复制代码