128. Longest Consecutive Sequenc

题目链接
tag:

• Hard；

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

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

思路：
  本题要求O(n)解决问题，我们可以借助哈希表，建立值与index的映射，随后遍历数组，针对每一个元素在哈希表中查找比它大的连续数的个数即可，代码如下：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return 1;
        unordered_map<int, int> m;
        for (int i=0; i<nums.size(); ++i) {
            m[nums[i]] = i;
        }
        int res = 0;
        for (int i=0; i<nums.size(); ++i) {
            int tmp_len = 1;
            int tmp_value = nums[i];
            while (true) {
                if (m.find(++tmp_value) != m.end())
                    ++tmp_len;
                else
                    break;
            }
            res = max(res, tmp_len);
        }
        return res;
    }
};