LeetCode128 Longest Consecutive Sequence

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

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)的时间复杂度，所以排序是不能用了。

用空间换时间，建立一个哈希表。对每一个元素把上下区间求出来，然后从hash表中删除。

代码：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, bool> hash;
        for (int i = 0; i < nums.size(); ++i) {
            hash[nums[i]] = true;
        }
        int result = 1;
        for (int i = 0; i < nums.size(); ++i) {
            int cur = nums[i];
            hash.erase(cur);
            int low = cur - 1, high = cur + 1;
            while (hash.find(low) != hash.end()) {
                hash.erase(low);
                low--;
            }
            while (hash.find(high) != hash.end()) {
                hash.erase(high);
                high++;
            }
            result = max(result, high - low - 1);
        }
        return result;
    }
};