128.Longest Consecutive Sequence

Tags: Array Hard

Links:https://leetcode.com/problems/longest-consecutive-sequence/

---

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.

---

Answer:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, bool> used;
        for (auto i : nums)
            used[i] = false;

        int longest = 0;

        for (auto i : nums){
            if (used[i])
                continue;

            int length = 1;

            for (int j = i + 1; used.find(j) != used.end(); ++j){
                used[j] = true;
                ++length;
            }

            for (int j = i - 1; used.find(j) != used.end(); --j){
                used[j] = true;
                ++length;
            }

            longest = max(longest, length);
        }

        return longest;
    }
};

解析：

如果先排序，则最优是$nlogn$，但是题目要求是$O(n)$，所以采用unordered_map，用一个bool型来记录每个数是否被使用过，对于没有被使用过的数，以它为中心向两个方向扩张。注意的一点是边界条件，longest初值应该设为0，因为可能传入的是一个空数组。