时间复杂度O(n)的非典型题解

本题第一时间想到的解法就是排序，但是这样不符合O(n)的时间复杂度要求。
另外一种思路就是用一个set记录每个元素的位置，然后遍历数组的元素，对每个元素做向上向下的遍历，统计连续的长度。
几个点：
1 普通的set查找是O(logN)的，改成hash set就可以认为是O(1)的了。
2 在之前序列统计过的数字就不需要再次统计了，用一个vector记录一下就flag可以了。

#include <unordered_map>

class Solution {
public:
    /**
     * 
     * @param num int整型vector 
     * @return int整型
     */
    int longestConsecutive(vector<int>& num) {
        int maxl = 0;
        unordered_map<int, int> um(num.size());
        vector<bool> visited(num.size(), false);

        for(int i = 0; i < num.size(); i++) um[num[i]] = i;
        for(int i = 0; i < num.size(); i++) {
            if(visited[i]) continue;
            int kk = 1;
            for(int n = num[i]+1; ; n++) {
                auto itr = um.find(n);
                if(itr != um.end()) {
                    int pos = itr->second;
                    visited[pos] = true;
                    kk++;
                } else break;
            }
            for(int n = num[i]-1; ; n--) {
                auto itr = um.find(n);
                if(itr != um.end()) {
                    int pos = itr->second;
                    visited[pos] = true;
                    kk++;
                } else break;
            }
            maxl = max(maxl, kk);
        }
        return maxl;
    }
};