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.
解释下题目：
找出数组中的最长序列的长度
1. 类似动态规划的思想
实际耗时：8ms
public int longestConsecutive(int[] nums) {
int res = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
continue;
}
int left = 0, right = 0;
if (map.containsKey(num - 1)) {
left = map.get(num - 1);
}
if (map.containsKey(num + 1)) {
right = map.get(num + 1);
}
int tmp = left + right + 1;
map.put(num, tmp);
map.put(num - left, tmp);
map.put(num + right, tmp);
res = Math.max(res, tmp);
}
return res;
}
题目中要求时间复杂度是O(n)，所以排序是断断不可能了的。也就是按序遍历下去，就能知道最大的解，那么就需要类似动态规划的结构，记录下每个数字的最大的答案，然后后面的数字出现了再去更新前面数字的解即可，所以想到用map这个数据结构。其实也不复杂，每当一个数字进来的时候，比如是5吧，我们就找比它小一的数字4和比它大一的数字6中记录的值，这两个值记录的是以4和6为边界的数组的长度，如果没有就是0。然后就能计算出这个数字5目前最大的边界，然后同时更新一下4和6的边界，最后在更新一下最大边界的值就可以了。
