LeetCode 128 Longest Consecutive Sequence

题目描述

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.

给定一个未排序的整数数组，找出（排序后）数组里面最长的连续元素序列（如[2, 3, 4, 5]）的长度

简单粗暴的做法就是排序后扫一遍统计长度，当然是 $O (N \log N)$ 排序之后 $O (N)$ 扫一遍统计长度，这样总体复杂度是 $O (N \log N)$ 。

维护当前已经组成的所有连续序列，每次将一个数组中的元素加入已有序列并更新当前的所有连续序列。扫描一遍原数组需要 $O (N)$ ，维护过程使用哈希表做到 $O (1)$ 实现总体 $O (N)$ 的复杂度。

读入一个数 x ，我们在HashMap中寻找其左边，其右边是否存在，存在的话返回其长度，不存在则置0

当前数的位置的长度，就是上一步中找到的两个长度的和再加1.

同时需要找到当前位置，最左边的边界和最右边的边界，根据刚刚得到的长度就可以计算出来，然后更新其值为上一步计算得到的值。

另外，考虑到性能，可以用unordered_set实现哈希表。