# 128. Longest Consecutive Sequence

[leetcode網址](https://leetcode.com/problems/longest-consecutive-sequence/description/)
## 問題
給你一個一維整數陣列`nums`，找到最長有連續整數的序列長度

Input: nums = [100,4,200,1,3,2]
Output: 4
        The longest consecutive elements sequence is [1, 2, 3, 4]. 
        Therefore its length is 4.

## Time = O (n) || Space = O(n)
### Idea
每次都去看左邊和右邊的連續數字的長度，兩邊長度再加自己，然後一直更新最長長度`length`
1. 檢查是否已經拜訪過
2. 檢查左邊是否有連續數字 ? 往左連續走的長度 : 0
3. 檢查右邊是否有連續數字 ? 往右連續走的長度 : 0
4. 現在長度更新 = 往左連續走的長度 + 往右連續走的長度 + 1(自己)
5. 更新往左走到底的長度，更新往右走到底的長度 -> 可能成為其他人的左邊或右邊連續數字
6. 更新最大長度 = max(length, current)

### Solution

int longestConsecutive(vector<int>& nums) {
    int length=0;
    unordered_map<int, int>map;
    for(auto&num: nums){
        if(map.count(num))continue;
        int left = map.count(num-1) ? map[num-1] : 0;
        int right = map.count(num+1) ? map[num+1] : 0;

        int current = left + right + 1;
        map[num] = current;

        map[num-left] = current;
        map[num+right] = current;
        length = max(current, length);
    }
    return length;
}

## Solution 2.
2025/12/19
太慢了，還用很多空間

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        priority_queue<int, vector<int>, less<int>>pq;
        unordered_set<int>numSet;

        for(auto num:nums){
            if(numSet.count(num))continue;
            numSet.insert(num);
            pq.push(num);

        }

        int maxLen=0;
        if(!pq.empty()){
            int len=1;
            maxLen=1;
            int prev=pq.top();
            pq.pop();
            while(!pq.empty()){
                int cur = pq.top();
                pq.pop();
                if(prev-cur == 1){
                    len++;
                }else{
                    len=1;
                }
                prev = cur;
                maxLen = max(maxLen, len);
            }
        }
        return maxLen;
    }
};