Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence. question link.

Given [100, 4, 200, 1, 3, 2],

The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Discussion

要求O(n)的复杂度，所以不能排序。要快速查找，所以想到用hash。给定num[i]，往两个方向找，count长度，同时找过的元素从hash中删除。

Solution

int longestConsecutive(vector<int> &num) {
        unordered_set<int> has_value(num.begin(), num.end());
        int len = 0;
        int max_len = 0;
        for(auto const& val : num) {
            int cur = val;
            while(has_value.find(cur) != has_value.end()) {
                len++;
                has_value.erase(cur);
                cur++;
            }
            //checking in the other way
            cur = val -1;
            while(has_value.find(cur) != has_value.end()) {
                len++;
                has_value.erase(cur);
                cur--;
            }
            //update result
            max_len = max(max_len, len);
            len = 0;
        }
        return max_len;
    }