力扣-128-最长连续序列

题目：
128. Longest Consecutive Sequence(hard)
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.

1 2 3 4

Example: Input: [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

题目大意：
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。

解题思路：
首先将数组中出现的数先写入哈希表中。
其次，只对当前数字 - 1不在哈希表中的数字，作为连续第一个数字去找对应的最长序列，因为其他数字一定已经出现在了某个序列里。
最后就是循环向后查找连续出现在哈希表中的数字即可。
代码参考官网给出的，上面说时间复杂度为O(n)，我怎么看都是O(n^2)啊… 郁闷。。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Java:
public int longestConsecutive(int[] nums){
    Set<Integer> set = new HashSet<>();
    for(int num : nums){
      set.add(num);
    }
    int longestStreak = 0;
    for(int num : set){
      if(!set.contains(num - 1)){
        int currentNum = num;
        int currentStreak = 1;

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

        longestStreak = Math.max(longestStreak,currentStreak);
      }
    }
    return longestStreak;
}