图解LeetCode——128. 最长连续序列

一、题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

二、示例

2.1> 示例 1：

【输入】nums = [100,4,200,1,3,2]

【输出】4

【解释】最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

2.2> 示例 2：

【输入】nums = [0,3,7,2,5,8,4,6,0,1]

【输出】9

提示：

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

三、解题思路

根据本题的描述，一般来说，最容易想到的就是先将nums进行排序，然后再从排序后的数组头部开始遍历，如果存在nums[i]+1，则进行加1计数。只要不存在nums[i]+1，则从0开始重新执行计数操作。那么，每当发生了“断点”，则通过result = Math.max(result, count)来更新result值（result表示最长数字连续序列个数）。

但是由于本题目要求实现时间复杂度为 O(n) 的算法解决此问题，那么排序的做法我们就无法实现了。那么，我们还有什么别的方法来解决这道题吗？我们可以创建一个Set数据结构的变量set，然后过滤掉nums数组中的重复元素。然后我们通过遍历数组nums，执行如下逻辑：

【case1】如果nums[i]+1在set中存在，则表示nums[i]不是连续序列的最大值，那么我们继续向下遍历，不用做任何操作；

【case2】如果nums[i]+1在set中不存在，则表示nums[i]是连续序列的最大值，那么我们执行倒序查找set中的元素，即：依次寻找nums[i]--的元素，并进行计数操作。

通过以上的操作，我们本质上就是去寻找连续序列的最大值，然后倒序寻找连续元素。对于非最大值，我们也不用处理，这样就可以加快查找速度了。当然，每次寻找完连续序列之后，再通过result = Math.max(result, count)来更新result值，那么最终结果就是本题要求的——最长数字连续序列长度了。

以上就是本题的解题思路了，还是按照惯例，我们以nums = [100,4,200,1,3,2]为例，看一下具体的处理流程。请见下图所示：

四、代码实现

class Solution {
    public int longestConsecutive(int[] nums) {
        int result = 0;
        Set<Integer> set = new HashSet();
        for (int num : nums) set.add(num);
        for (int num : nums) {
            if (!set.contains(num + 1)) {
                int max = 0;
                while(set.contains(num--)) max++;
                result = Math.max(result, max);
            }
        }
        return result;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」