[LeetCode從零單刷]Longest Consecutive Sequence

題目：

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

解答；

O(n) 的時間復雜度看到，就猜到是不是用動態規劃。然後想了很長時間找不到狀態轉移方程……

結果 Discuss 裡面都是用容器來計算（O(n) 不一定是DP，也可以考慮容器）。因為這段序列可能是有重復元素的，所以使用 set 相關的容器可以避免容器中包含重復元素。

但是，set / map 是基於紅黑樹實現的，因此查找效率是 O(log n) 級別的；因此，可以使用基於 hashmap 的 unordered_set 容器，查找效率是常數級別。

設定一個容器，保存已經訪問過的元素。每個元素遍歷它 ++ 以及 -- 部分。

class Solution {
public:
    int longestConsecutive(vector& nums) {
        unordered_set visited;
        unordered_set all(nums.begin(), nums.end());
        
        int max = 0;
        int count, tmp;
        int size = nums.size();
        for(int i=0; i max) max = count;
        }
        return max;
    }
};