leetcode地址：
https://leetcode.com/problems/longest-consecutive-sequence/description/
难度：hard
描述：
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.
解题思路：
这题说难不难，说简单也不简单。简单的地方在于它的解法一点也不复杂，很容易理解，难的地方在于如果之前没有做过类似的题，可能一下子不容易想到。
我们可以这么看这个问题，这个数组中的所有的数肯定是由一系列的连续值组成的。可以想象将数组排序后，中间会有一些跳跃的点，从而将整个数组分隔成一个个短的连续值。我们的目的就是要找出整个短的连续值中长度最长的那个。以一个连续值组内的任意一个数字为切入点，我们最终都应该能找到这个连续组，所以对于一个小的连续组，我们只需要以其中的任意一个数字为切入点，不需要重复地遍历到每个数字，那样就会造成大量的重复计算。
我们的算法具体步骤如下：
首先将数组的数字存入一个HashSet中；
然后遍历数组，如果当前的数字在hashSet中不存在，说明它所在的连续组已经被处理过了，因此直接进入下一个循环。
如果当前数字存在，那么我们接下来以这个数组为切入点，分别向前和向后连续查找，知道set中找不到连续值为止，此时我们就找到了当前数字所在的连续组，计算它的长度，与记录的最大长度比较，如果当前的长度更长，就更新记录的最大长度值。
完成遍历就找到了最大长度。
代码：
public int longestConsecutive(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
set.add(nums[i]);
}
int longest = 0;
for (int i = 0; i < nums.length; i++) {
if (!set.contains(nums[i])) {
continue;
}
int cur = nums[i];
int len = 1;
set.remove(cur);
int pre = cur - 1, next = cur + 1;
while (set.contains(pre)) {
set.remove(pre);
len++;
pre--;
}
while (set.contains(next)) {
set.remove(next);
len++;
next++;
}
if (len > longest) {
longest = len;
}
}
return longest;
}
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.