Longest Consecutive Sequence

LeetCode #128

Description:

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

Your algorithm should run in O(n) complexity.

Example:

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Idea:

如果允许 O(nlogn) 的复杂度，那么可以先排序，可是本题要求 O(n)。 由于序列里的元素是无序的，又要求 O(n)，首先要想到用哈希表。 用一个哈希表 unordered_map<int, bool> used 记录每个元素是否使用，对每个元素，以该 元素为中心，往左右扩张，直到不连续为止，记录下最长的长度。

Code:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, bool> hashTable;

        for(auto e : nums){
            hashTable[e]=false;
        }

        int max_len=0;
        int len=0;

        for(int i=0; i<nums.size(); ++i){
            if(!hashTable[nums[i]]){
                len = 1;
                hashTable[nums[i]] = true;
                for(int j=nums[i]+1; hashTable.find(j)!=hashTable.end(); j++){
                    hashTable[j]=true;
                    len++;
                }
                for(int j=nums[i]-1; hashTable.find(j)!=hashTable.end(); j--){
                    hashTable[j]=true;
                    len++;
                }
                max_len = max(max_len, len);
            }
        }

        return max_len; 
    }
};