最长连续序列

发表于 分类于 阅读次数：

最长连续序列（难度：困难）

1579513410172

方法：哈希表（HashSet）

因为一个序列可能在 nums 数组的任意一个数字开始，我们可以枚举每个数字作为序列的第一个数字，搜索所有的可能性 （暴力法）。优化：将数组中的数字用HashSet保存，实现O(1)的时间查询，同时，我们只对 当前数字 - 1 不在哈希表里的数字，作为连续序列的第一个数字去找对应的最长序列，这是因为其他数字一定已经出现在了某个序列里。

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
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length <= 1)
            return nums.length;
            
        HashSet<Integer> hashSet = new HashSet<>();
        for(int num:nums)
            hashSet.add(num);
        
        int maxLen = 1;

        for(int i = 1; i < nums.length; i++){
            int curLen = 1;
            if(!hashSet.contains(nums[i]-1)){
                int curNum = nums[i];
                while(hashSet.contains(curNum+1)){
                    curLen++;
                    curNum++;
                }
            }
            maxLen = Math.max(maxLen,curLen);
            
        }
        return maxLen;        
    }
}
复杂度

时间复杂度：O(n)。尽管在 for 循环中嵌套了一个 while 循环，时间复杂度看起来像是二次方级别的。但其实它是线性的算法。因为只有当 curNum 遇到了一个序列的开始， while 循环才会被执行（也就是 curNum-1 不在数组 nums 里）， while 循环在整个运行过程中只会被迭代 n 次。这意味着尽管看起来时间复杂度为 O(n⋅n) ，实际这个嵌套循环只会运行O(n+n)=O(n) 次。所有的计算都是线性时间的，所以总的时间复杂度是 O(n)的。

空间复杂度：O(n)。为了实现 O(1)的查询，我们对哈希表分配线性空间，以保存 nums 数组中的 O(n)个数字。