題目描述：給一個未排序的整數(shù)數(shù)組，查找其中最長連續(xù)元素序列的長度。如[100, 4, 200, 1, 3, 2]找到[1, 2, 3, 4]，返回4。要求復雜度為O(n)。

分析：由于限定了線性復雜度所以不能用排序了。第一個想法是設一個長度為給定的數(shù)組中最大數(shù)mx的標記數(shù)組，記錄給定數(shù)組中從0～mx 的元素是否出現(xiàn)，然后遍歷一遍標記數(shù)組，找連續(xù)1的最長長度。提交發(fā)現(xiàn)數(shù)據(jù)存在負數(shù)，思考不全面。還是用map來記錄。

代碼：雖然是兩重循環(huán)，但實際上最多只會遍歷數(shù)組一次。因為對一個數(shù)左右的查找是連續(xù)的，而子序列是有斷點的。故復雜度為O(n)。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {

        //無序容器，快速查找刪除，不擔心略高的內(nèi)存時用unordered_map；有序容器穩(wěn)定查找刪除效率，內(nèi)存很在意時候用map。
        unordered_map<int, bool> used;

        //遍歷nums，i是其中元素，類似Python 中for i in nums 的用法
        for (auto i : nums)
            used[i] = false;
        int longest = 0;

        for (auto i : nums)
        {
            if (used[i]) continue;            //已經(jīng)遍歷過
            int len = 1;
            for (int j = i + 1; used.find(j) != used.end(); j++)            //查找比 i 大的部分
            {
                used[j] = true;
                len ++;
            }
            for (int j = i - 1; used.find(j) != used.end(); j--)
            {
                used[j] = true;
                len ++;
            }
            longest = max(longest, len);
        }
        return longest;
    }
};