# 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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/6.array/128.-longest-consecutive-sequence-m.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.