###### tags: `LeetCode` `Medium`
# LeetCode #128 [Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/)
### (Medium)
給定一個未排序的整數數組 nums ，找出數字連續的最長序列（不要求序列元素在原數組中連續）的長度。

請你設計並實現時間複雜度為 O(n) 的算法解決此問題。

---
若不考慮時間複雜度, 則直接排序nums, 然後遍歷, 若nums[i]連續則計數器+1, 直到斷檔, 更新最大連續數量。便利完成後即可得到答案。

時間複雜度為O(nlogn)(排序時間)

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

---
O(n)的作法(1):
創建一Hash表(unordered_map), 將nums[i]依次放入並檢查左右是否存在, 若左右存在則代表nums[i]成為橋梁, 該連續長度變為左長度+右長度+1, 若左邊或右邊只存在一邊, 則包含nums[i]的連續長度變為左(或右)長度+1, 並且隨時更新最大值, 遍歷完整個nums即可得到答案。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.size()){
            unordered_map<int,int> check;
            int ans=INT_MIN;
            for(int n:nums){
                if(check.count(n))continue;
                auto lit=check.find(n-1);
                auto rit=check.find(n+1);
                int l=(lit==check.end())?0:lit->second;
                int r=(rit==check.end())?0:rit->second;
                    
                check[n]=l+r+1;
                check[n+r]=l+r+1;
                check[n-l]=l+r+1;
                
                ans=max(ans, l+r+1);
            }
            return ans;
        }
        return 0;
    }
};

---
直接把nums塞進Hash表裡並尋找若nums[i+1]存在則計數器+1直到斷檔, 要注意的是時間複雜度因為找過的數在下一次尋找時會直接被跳過, 所以整體來說時間複雜度仍然是O(n)。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.size()){
            unordered_set<int> check(nums.begin(),nums.end());
            int ans=INT_MIN;
            for(int n:check){
                if(!check.count(n-1)){
                    int cnt=0;
                    while(check.count(n++))cnt++;
                    ans=max(ans,cnt);
                }
            }
            return ans;
        }
        return 0;
    }
};