描述 Description

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.

[Longest Consecutive Sequence]

分析 Analysis

如果允许O(nlogn)的复杂度，那么可以先排序，可是本题要求O(n)。由于序列里的元素是无序的，又要求O(n)，首先要想到用哈希表。

方法1

用一个哈希表存储所有出现过的元素，对每个元素，以该元素为中心，往左右扩张，直到不连续为止，记录下最长的长度。

连续的都记录完成后，将连续的元素都从哈希表中删除。

时间复杂度O(n)。

方法2（lz更推荐其c++实现）

使用HashMap。主要思路是将序列的长度保存在序列两端，因为序列内部已经和maxlength比较过，再来一个内部的点直接continue。比如序列 {1, 2, 3, 4, 5}, map.get(1) 和map.get(5) 都应该返回 5。

每遍历一个新元素，都要做两件事：

1. See if n - 1 and n + 1 exist in the map, and if so, it means there is an existing sequence next to n. Variables left and right will be the length of those two sequences, while 0 means there is no sequence and n will be the boundary point later. Store (left + right + 1) as the associated value to key n into the map.
2. Use left and right to locate the other end of the sequences to the left and right of n respectively, and replace the value with the new length.

时间复杂度O(n)。

代码 Code

方法1

class Solution {
public:
    int longestConsecutive(const vector<int> &nums) {
        unordered_set<int> my_set;
        for (auto i : nums) my_set.insert(i);

        int longest = 0;
        for (auto i : nums) {
            int length = 1;
            for (int j = i - 1; my_set.find(j) != my_set.end(); --j) {
                my_set.erase(j);
                ++length;
            }
            for (int j = i + 1; my_set.find(j) != my_set.end(); ++j) {
                my_set.erase(j);
                ++length;
            }
            longest = max(longest, length);
        }
        return longest;
    }
};

方法2

(c++)

class Solution {
public:
int longestConsecutive(vector<int> &num) {
    unordered_map<int, int> m;
    int r = 0;
    for (int i : num) {
        if (m[i]) continue;
        r = max(r, m[i] = m[i + m[i + 1]] = m[i - m[i - 1]] = m[i + 1] + m[i - 1] + 1);
    }
    return r;
}
};

（java）

public int longestConsecutive(int[] num) {
    int res = 0;
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int n : num) {
        if (!map.containsKey(n)) {
            int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
            int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
            // sum: length of the sequence n is in
            int sum = left + right + 1;
            map.put(n, sum);

            // keep track of the max length 
            res = Math.max(res, sum);

            // extend the length to the boundary(s)
            // of the sequence
            // will do nothing if n has no neighbors
            map.put(n - left, sum);
            map.put(n + right, sum);
        }
        else {
            // duplicates
            continue;
        }
    }
    return res;
}