128. Longest Consecutive Sequence

leetcode網址

問題

給你一個一維整數陣列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;
}