Leetcode 128: 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），我们可以想到排序算法，线性排序算法 bucket sort, 最后排序出来找最长连续子序列就可以了，这是最直接的想法，时间复杂度： O(n), 空间复杂度O(n)

但是在网上看到别人的解法，发现比bucket sort 来解简单很多， 用一个unordered_set， 由于unordered_set的insert, erase, find的时间复杂度都是O(1), 所以是很喜欢用的一个STL container, 首先把这些数字都放进unordered_set里面，然后对于array里面的每一个element, 在unordered_set里面往增1，减一两个方向找连续的值，如果这些连续的值存在于unordered_set中，那么就记录以这个element为中心连续值的个数，每次找到一个连续值就需要在set中把这个值erase, 为了防止后面的重复运算，并且更新此时的global_max。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        unordered_set<int> buf;
        int rst = 1;
       
        for (int i : nums) {
            buf.insert(i);
        }
       
        for (int i : nums) {
            int left = i-1;
            int right = i+1;
            int count = 1;
            while (buf.find(left) != buf.end()) {
                count++;
                buf.erase(left);
                left--;
            }
            while (buf.find(right) != buf.end()) {
                count++;
                buf.erase(right);
                right++;
            }
            rst = max(count, rst);
        }
        return rst;
    }
};