最长连续序列[中等]

优质博文：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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

【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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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