LeetCode/solutions/128. Longest Consecutive Sequence.md

# [128. Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/)

# 思路

给定一个无序的数组，找出最长的可组成连续序列的元素的个数，要求时间复杂度为O(n)。

## 思路一

看看暴力法怎样解此题：遍历一遍数组，对每个数num，我们假设num就是某个连续范围的最小值，所以我们需要判断num+1、num+2...是否在数组中。可见这样的时间复杂度为O(n^2)。

我们可以对暴力法优化一下：
* 由于要经常判断某个元素是否在数组中，所以我们可以事先用一个hash存放每个元素，查找复杂度为O(1)；
* 对于某个元素num，如果 num-1 也在数组中，直接跳过就可以了，因为我们处理 num-1 时就会处理到num、num+1...。即如果num是某个候选范围的起点时（即num-1不在数组中），我们才不断判断num+1、num+2...是否在数组中。

虽然有两层循环，但是每个范围只会被遍历一次，所以总的复杂度为O(n)

## 思路二

这题其实可以看做是区间合并的问题，可以采取类似并查集的思路。我们用一个名为mp的hashmap记录以这个数为端点(可能左也可能右端点)的连续范围的长度，例如果`mp[4] = 2`，说明存在一个以4为左端点的长度为2的连续范围（即4、5），或者存在一个以4为右端点的长度为2的连续范围（即3、4）。但是值得注意的是，如果数num不在某个范围的端点，那么`mp[num]`的值没有意义，我们也不会用它。

那么如果我们遍历到了数num，该怎样求得`mp[num]`呢。
* 首先如果之前已经遇到过num了，那直接跳过即可；
* 否则我们可以查看num-1和num+1是否之前出现过：
    * 如果出现过num-1，那么`mp[num-1]`一定表示以num-1为右端点的范围长度（因为num之前没出现过，所以num-1不可能是左端点，下同）；
    * 如果出现过num+1，那么`mp[num+1]`一定表示以num+1为左端点的范围长度；
    
    所以num可把左右两个范围连成一个大小为`mp[num-1] + mp[num+1] + 1`的范围，因此需要更新该大范围的左端点的值`mp[num - mp[num-1]]`和右端点的值`mp[num + mp[num+1]]`。至于`mp[num]`等于什么无关紧要，因为我们不需要用除了端点之外的值，所以我们随便赋一个值给`mp[num]`就行了，仅仅表明已经出现num了。

本思路相比于思路一的优势在于无需先将所有元素用一个hash存着，所以适合数组动态增长的情况。

只需要遍历一遍数组，所以总的时间复杂度为O(n)

# C++
## 思路一
``` C++
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int>num_set(nums.begin(), nums.end());
        int n = num_set.size();
        if(n <= 1) return n;
        
        int res = 1;
        for(int num: num_set){
            if(!num_set.count(num - 1)){ // 如果num是起点
                int cur_res = 1;
                while(num_set.count(num + cur_res)) cur_res++;
                res = max(cur_res, res);
            }
        }
        return res;
    }
};
```

## 思路二
``` C++
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        //mp[num] = i 表示以num为端点(可能左也可能右端点)的连续范围的长度
        unordered_map<int, int>mp;
        int n = nums.size();
        if(n <= 1) return n;
        
        int res = 1;
        for(int num: nums){
            if(mp.count(num)) continue; // 这表明num已经出现过
            
            // 如果 mp.count(num-1) == 1 说明以num-1为右端点的连续范围长度为mp[num-1]
            int l = mp.count(num - 1) ? mp[num - 1] : 0;
            // 如果 mp.count(num+1) == 1 说明以num+1为左端点的连续范围长度为mp[num-1]
            int r = mp.count(num + 1) ? mp[num + 1] : 0;
            
            int total = r + l + 1; // 左右两个连续范围组成一个大的连续范围
            res = max(res, total);
            
            mp[num] = -1; // 这里可以赋成任意值, 因为我们不会用除了端点之外的值
        
            mp[num - l] = total; // 更新大范围的左端点的值
            mp[num + r] = total; // 更新大范围的右端点的值
        }
        return res;
    }
};
```