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

# Longest Consecutive Sequence

## Longest Consecutive Sequence

原题链接：<https://leetcode.com/problems/longest-consecutive-sequence/>

### 描述

> Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
>
> Your algorithm should run in O(*n*) complexity.

### 例子

> Input: \[100, 4, 200, 1, 3, 2]&#x20;
>
> Output: 4&#x20;
>
> Explanation: The longest consecutive elements sequence is \[1, 2, 3, 4]. Therefore its length is 4

### 解法一&#x20;

**暴力破解**

```cpp
class Solution {
private:
    bool arrayContains(const vector<int>& nums, int num){
        for(auto n: nums){
            if(n==num)return true;
        }
        return false;
    }
public:
    int longestConsecutive(vector<int>& nums) {
        int longestLen=0;
        for(int n : nums){
            int currNum=n;
            int currLen=1;
            while(arrayContains(nums, currNum+1)){
                currNum++;
                currLen++;
            }
            longestLen=max(longestLen, currLen);
        }
        return longestLen;
    }
};
```

**分析：**

结&#x679C;**：超时**

### 解法二

**排序**

```cpp
class Solution {
private:
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.size() == 0)return 0;
        sort(nums.begin(),nums.end());
        int longestLen=1;
        int currLen=1;
        for(int i=1; i<nums.size(); i++){
            if(nums[i]!=nums[i-1]){
                if(nums[i] == nums[i-1]+1){
                    currLen++;
                }else{
                    longestLen = max(longestLen, currLen);
                    currLen=1;
                }
            }
        }
        return max(longestLen, currLen);
    }
};
```

### 解法三

**哈希**

使用unordered\_set

```cpp
class Solution {
private:
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.size() == 0)return 0;
        unordered_set<int> seen;
        for(int n:nums){
            seen.insert(n);
        }
        int longestLen=0;
        
        for(int n:nums){
            if(!seen.count(n-1)){
                int currNum=n;
                int currLen=1;
                while(seen.count(currNum+1)){
                    currNum++;
                    currLen++;
                }
                longestLen = max(longestLen, currLen);
            }
        }
        return longestLen;
    }
};
```

使用unordered\_map

```cpp
class Solution {
    public:
    int longestConsecutive(const vector<int> &nums) { 
        unordered_map<int, bool> used;                                             
        for (auto i : nums) used[i] = false;
        int longest = 0;
        for (auto i : nums) {
            if (used[i]) continue;
            int length = 1;
            used[i] = true;
            for (int j = i + 1; used.find(j) != used.end(); ++j) { 
                used[j] = true;
                ++length; 
            }
            for (int j = i - 1; used.find(j) != used.end(); --j) { 
                used[j] = true;
                ++length; 
            }
            longest = max(longest, length); 
        }
        return longest;
      }
};
```

## 总结