Given an unsorted array of integers, find the length of the longest consecutive elements sequence. （Hard）
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.
分析：
要做到O(n)的时间复杂度，所以排序是不能用了。
用空间换时间，建立一个哈希表。对每一个元素把上下区间求出来，然后从hash表中删除。
代码：
1 class Solution { 2 public: 3 int longestConsecutive(vector<int>& nums) { 4 unordered_map<int, bool> hash; 5 for (int i = 0; i < nums.size(); ++i) { 6 hash[nums[i]] = true; 7 } 8 int result = 1; 9 for (int i = 0; i < nums.size(); ++i) { 10 int cur = nums[i]; 11 hash.erase(cur); 12 int low = cur - 1, high = cur + 1; 13 while (hash.find(low) != hash.end()) { 14 hash.erase(low); 15 low--; 16 } 17 while (hash.find(high) != hash.end()) { 18 hash.erase(high); 19 high++; 20 } 21 result = max(result, high - low - 1); 22 } 23 return result; 24 } 25 };
LeetCode128 Longest Consecutive Sequence
原文：http://www.cnblogs.com/wangxiaobao/p/6135677.html