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

# 128. Longest Consecutive Sequence

## problem description

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

**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.
```

## algorithm thought

这里要求需要使用O(n)时间求解，我们必须引入一个新的数据结果来使访问一个数据的时间控制到O(1)时间。那肯定是unordered\_set类型，这个数据结构是基于hashmap实现的，插入和查询时间是O(1)。首先我们将所有数据存入set，然后顺序遍历原来的数组，如果数字的前一个在set中存在，continue，否则，表示这个数字是这段数字的开始，于是从这里开始顺序加一，每次结果在set中查询，知道不存在这个数字。最后求最长的解

## code

```cpp
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(),nums.end());
        int best=0;
        for(int val:nums)
        {
            if(s.count(val-1)) continue;
            int y=val+1;
            while(s.count(y))
            {
                y++;
            }
            best=max(best,y-val);            
        }
        return best;
    }
};
```

## algorithm analysis

开始将vector数据复制到unordered\_set中，时间复杂度O(n).注意一定要使用这种办法而不是一个个插入的方法，如果一个个插入很可能耗时更多。然后遍历数组时间复杂度O(n),在循环中会再次遍历一遍顺序的数字，这里需要执行n次。 最后执行3n次，时间复杂度O(n)