# 128 - Longest Consecutive Sequence

解法一 - Sorting 完，直接算最長連續長度

這個解法滿直觀的，實作如下：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.empty())
            return 0;

        sort(nums.begin(), nums.end());

        int longestStreak = 1;
        int currentStreak = 1;

        for(int i=1; i<nums.size(); i++) {
            // Even duplicate happens, we don't need to reset currentStreak
            if(nums[i] != nums[i-1]) {
                if(nums[i] == nums[i-1]+1) {
                    currentStreak++;
                }
                else {
                    longestStreak = max(longestStreak, currentStreak);
                    currentStreak = 1;
                }
            }
        }

        return max(longestStreak, currentStreak);
    }
};

不過這個解法的 time complexity 是 O(nlogn)，不符合題目要求。

解法二 - Hash set 解法

在討論區看到一個超聰明的解法，我們可以先把所有的數字儲存到 Hash Set 裡，之後就開始走過所有數字，如果這個數字的前一個跟後一個都有在 Hash Set 中，就把這些數字刪掉，然後繼續擴張，直到找完這一個 streak 的所有數字。

因為 Hash Set 的 find 只需要 O(1)，所以是一個 O(n) 的演算法。實作如下：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> record(nums.begin(),nums.end());
        int res = 1;

        for(int n : nums){
            if(record.find(n)==record.end()) continue;

            record.erase(n);

            int prev = n-1,next = n+1;
            while(record.find(prev)!=record.end()) record.erase(prev--);
            while(record.find(next)!=record.end()) record.erase(next++);

            res = max(res,next-prev-1);
        }

        return res;
    }
};

跑起來的效率如下：

Runtime: 8 ms, faster than 95.12% of C++ online submissions for Longest Consecutive Sequence. Memory Usage: 9.9 MB, less than 90.38% of C++ online submissions for Longest Consecutive Sequence.