最长连续序列[中等]

优质博文：IT-BLOG-CN

一、题目

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

0 <= nums.length <= 105
-109 <= nums[i] <= 109

二、代码

【1】我们首先先当的是非O(n)的方法，对nums进行排序后判断最长连续序列。

class Solution {public int longestConsecutive(int[] nums) {// 我们首先想到的就是非O(N)的时间复杂度，先排序，在去重。if (nums == null || nums.length == 0) {return 0;}Arrays.sort(nums);Set<Integer> set = new LinkedHashSet<>();for (int i = 0; i < nums.length; i++) {set.add(nums[i]);}int maxLen = 1;int count = 1;int pre = Integer.MIN_VALUE;for (int num : set) {if (num - pre == 1) {count++;} else {count = 1;}pre = num;maxLen = Math.max(maxLen, count);}return maxLen;}
}

【2】上面的方法不是O(n)时间复杂度，所以我们需要将排序和去重这个动作的O(nlogn)的复杂度降下来，可以通过哈希表存储数组中的数，这样查一个数是否存在就可以优化至O(1)的时间复杂度，仅仅是这样我们的算法时间复杂度最坏情况下还是会达到O(n2)（即外层需要枚举O(n)个数，内层需要暴力匹配O(n)次），无法满足题目的要求。但仔细分析这个过程，我们会发现其中执行了很多不必要的枚举，如果已知有一个x,x+1,x+2,⋯ ,x+y的连续序列，而我们却重新从x+1，x+2或者是x+y处开始尝试匹配，那么得到的结果肯定不会优于枚举x为起点的答案，因此我们在外层循环的时候碰到这种情况跳过即可。

增加了判断跳过的逻辑之后，时间复杂度是多少呢？外层循环需要O(n)的时间复杂度，只有当一个数是连续序列的第一个数的情况下才会进入内层循环，然后在内层循环中匹配连续序列中的数，因此数组中的每个数只会进入内层循环一次。根据上述分析可知，总时间复杂度为O(n)，符合题目要求。

class Solution {public int longestConsecutive(int[] nums) {// 我们首先想到的就是非O(N)的时间复杂度，先排序，在去重。if (nums == null || nums.length == 0) {return 0;}Set<Integer> num_set = new HashSet<>();for (int i = 0; i < nums.length; i++) {num_set.add(nums[i]);}int maxLen = 0;for (int num : num_set) {// 先判断是否存在上一个数字，减少时间复杂度if (!num_set.contains(num - 1)){int count = 1;int currentNum = num;while (num_set.contains(currentNum + 1)) {currentNum += 1;count += 1;}maxLen = Math.max(maxLen, count);}}return maxLen;}
}

时间复杂度： O(n)，其中n为数组的长度。具体分析已在上面正文中给出。
空间复杂度： O(n)。哈希表存储数组中所有的数需要O(n)的空间。