> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/6.array/128.-longest-consecutive-sequence-m.md).

# 128. Longest Consecutive Sequence (M)

Given an unsorted array of integers `nums`, return *the length of the longest consecutive elements sequence.*

You must write an algorithm that runs in `O(n)` time.

 

**Example 1:**

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

**Example 2:**

```
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
```

 

**Constraints:**

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

### Solution:

<https://www.jiuzhang.com/problem/longest-consecutive-sequence/>

**Version 1:**&#x20;

既然要O(n)算法，排序显然不行，所以自然想到用hash table。将序列中的所有数存到一个unordered\_set中。对于序列里任意一个数A\[i]，我们可以通过set马上能知道A\[i]+1和A\[i]-1是否也在序列中。如果在，继续找A\[i]+2和A\[i]-2，以此类推，直到将整个连续序列找到。为了避免在扫描到A\[i]-1时再次重复搜索该序列，在从每次搜索的同时将搜索到的数从set中删除。直到set中为空时，所有连续序列搜索结束。

复杂度：由于每个数字只被插入set一次，并删除一次，所以算法是O(n)的。

```
public class Solution {
    /**
     * @param nums: A list of integers
     * @return an integer
     */
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        
        int longest = 0;
        for (int i = 0; i < nums.length; i++) {
            int down = nums[i] - 1;
            while (set.contains(down)) {
                set.remove(down);
                down--;
            }
            
            int up = nums[i] + 1;
            while (set.contains(up)) {
                set.remove(up);
                up++;
            }
            
            longest = Math.max(longest, up - down - 1);
        }
        
        return longest;
    }
}
```

\
**Version 2:**&#x20;

* 相比标准答案，此解是**one pass solution**
* 用一个HashMap来记录还有数字i的连续序列的长度，该长度等于左右连续序列长度的和加 - count(i) = count(i - 1) + count(i + 1) + 1
* **需要注意的是**，当加入一个数字i的时候，除了要利用上面公式更新该点的序列长度以外，还要把它**左边和右边连续序列端点**对应的长度改掉 举个例子：4(1)表示含有数字4的连续序列长度是1 [4,5,3,1,2](https://www.jiuzhang.com/problem/longest-consecutive-sequence/) => 4(1) => 4(2), 5(2) => 4(2), 5(3), 3(3) => 4(2), 5(3), 3(3), 1(1) => 4(2), 5(5), 3(3), 1(5), 2(5)

```
public class Solution {
    /**
     * @param num: A list of integers
     * @return: An integer
     */
    public int longestConsecutive(int[] num) {
        // write your code here
        if (num == null || num.length == 0) {
            return 0;
        }
        
        Map<Integer, Integer> streak = new HashMap<>();
        
        int max = 0;
        for (int n : num) {
            if (streak.containsKey(n)) {
                continue;
            }
            int leftCount = 0, rightCount = 0;
            if (streak.containsKey(n - 1)) {
                leftCount = streak.get(n - 1);    
            }
            if (streak.containsKey(n + 1)) {
                rightCount = streak.get(n + 1);
            }
            int count = leftCount + rightCount + 1;
            max = Math.max(max, count);
            streak.put(n, count);
            streak.put(n - leftCount, count);
            streak.put(n + rightCount, count);
        }
        
        return max;
    }
}
```

**Version 3:**&#x20;

pq排了一下序， set去了一下重复， 剩下就没啥难度了， 应该算O(N)的吧

```
public class Solution {
    /**
     * @param num: A list of integers
     * @return: An integer
     */
    public int longestConsecutive(int[] num) {
        // write your code here
        if (num == null || num.length == 0) {
            return 0;
        } 
        
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < num.length; i++) {
            if (!set.contains(num[i])) {
                set.add(num[i]);
                pq.offer(num[i]);
            }
        }
        
        int res = 1;
        int temp = 1;
        int start = pq.poll();
        while (!pq.isEmpty()) {
            int curr = pq.poll();
            if (curr == start + 1) {
                start = curr;
                temp++;
            } else {
                temp = 1;
                start = curr;
            }
            res = Math.max(res, temp);
        }
        
        return res;
    }
}
```