LeetCode: Longest Consecutive Sequence

思路分析

虽然难度标识为Hard，但其实是个水题。这种题目显然排序可做，但是复杂度O(n*logn)。既然要求O(n)，也就是扫描一遍数组的复杂度，肯定是用到了某种特殊的数据结构。在这个题目里面，显然用的就是哈希表了。

我们这样考虑，首先用神器unordered_map哈希一下所有输入的整数，然后遍历输入的每个整数，如果哈希表中还有它，那么就在数轴上以这个数字为中心，不断往两边+-1检查是否存在对应的数字。这样我们就在数轴上找到了一个连续段，并且更新最大长度之后要从哈希表中删除这个连续段即可。注意最短长度为1。

代码

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        int ans = 0;
        unordered_map<int, bool> _hash;
        rep(i, num.size()) _hash[num[i]] = true;
        rep(i, num.size()) if ( _hash[num[i]] ) {
            int len = 1;
            int upper = num[i] + 1, lower = num[i] - 1;
            while ( _hash[upper] ) {
                _hash[upper] = false;
                upper++;
                len++;
            }
            while ( _hash[lower] ) {
                _hash[lower] = false;
                lower--;
                len++;
            }
            _hash[num[i]] = false;
            ans = max(ans, len);
        }
        return ans;
    }
};