1.问题
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
提示
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
2.解题思路
2.1 先排序后遍历再判断
先对数组进行升序排列，则若存在连续序列，当遍历到某一值时，其前后之差应该为1，则进行最长序列长度统计；若不为1，如果相等，则跳过此值，进行下一个循环；如果不等，则不连续，当前统计的连续序列长度置为1。见方法longestConsecutive2。
此方法，虽然看似时间复杂度为O(N)，其实排序就占用了至少O(N)，还是不是很理想的算法。
2.2 哈希表
定义一哈希表，key为数组中的元素，value为当前元素所在连续序列的长度。
对于不存在于哈希表中的元素：
- 取出其左右相邻数已有的连续区间长度 left 和 right
- 计算当前数的区间长度为：
cur_length = left + right + 1 - 根据 cur_length 更新最大长度 max_length 的值
- 更新区间两端点的长度值
例如，key = 5， value = 3，意味着对于5来说，有一个长度为3的连续区间，5属于这个区间(不要纠结5这个元素到底在该区间的哪个位置) 具体来说，这个连续区间可能是[4, 6], [3, 5], [5,7]都是满足定义的，具体看nums里有哪些元素。
如果对于元素 num=5，在判断 !map.contains(num) 时，其不存在于哈希表中，即第一次遍历到5这个元素，则对于可能存在的连续序列，num-1若出现在序列当中，则其范围应为[num-value, num-1]. 比如：上述元素5，则4所在范围只能是[4-value, 4]，如果不是，那5必在其中，不符合我们的循环条件。这里value表示4所对应的连续序列长度。
同样道理，对于6，其出现的范围只能是[6, 6+value]；这里value表示6所对应的连续序列长度。详见代码中方法longestConsecutive。
接着需要将之前计算的合并长度进行赋值，并且只要赋值给端点就行了，这是因为整个子序列 [num-left, num+right] 中的元素都已经被访问过了所有的值都已经存储到了map里面，那么如果其他数字想要通过这个判断 !map.contains(num) ，这个数字只可能在这个子序列的左边或者右边.
我们还是以左边为例，当我们放入第num-left-1个数字的时候就需要知道我们的右边第num-left的子序列长度，而通过之前的计算 map[num - left] = cur_length我们可以知道第num-left为开头的最大子序列长度为cur_length, 可以看出左端点（num-left）的值只有其左边的数字用的上，那么他自己自然只需要存右边的子序列长度就可以了，右边同理。
2.3 HashSet
- 通过HashSet将不重复的元素入库
- 遍历数组，判断当前num减去1的元素是否已存在：
- 如果不存在，并且num+当前连续序列最大长度的值存在于HashSet中，统计连续序列长度
- 否则，跳过该元素。这里循环的条件目的就是找到连续序列的起始元素，找到后，才开始统计最大的连续序列长度
详见代码中方法longestConsecutive3。不过此算法由于用到HashSet，其时间复杂度不符合题目中所需O(N)的条件。
3.代码
class Solution {
//1.先排序
//2.连续序列差值为1，统计连续序列长度
//3.否则，相等的话，继续循环遍历；不等，重新计数连续序列长度
public int longestConsecutive2(int[] nums) {
//判空
if(null==nums || nums.length==0){
return 0;
}
//只有一个
if(1==nums.length){
return 1;
}
//排序
Arrays.sort(nums);
//结果
int maxLength=1;
//初始最长连续序列长度
int current=1;
for(int i=1;i<nums.length;i++){
//是否相差1
if(nums[i]-nums[i-1]==1){
current++;
maxLength=Math.max(maxLength, current);
}
//相等
else if(nums[i]==nums[i-1]){
continue;
}
//不等，重新统计
else{
current=1;
}
}
return maxLength;
}
public int longestConsecutive3(int[] nums) {
// 遍历数组，构造哈希集合，去重记录出现过的数字
HashSet<Integer> numSet = new HashSet<>();
for (int num : nums) {
numSet.add(num);
}
int maxLength=0;
int currentLength=1;
for(int num : nums){
//当前数字不是其可能所在连续序列的最小值，则略过；否则向上循环寻找num+1，记录长度
//如果当前num+当前最大长度不在哈希表里，那这次循环就不用看了
if(!numSet.contains(num-1) && numSet.contains(num+maxLength)){
currentLength=1;
while(numSet.contains(num+1)){
currentLength++;
num++;
}
if(currentLength>maxLength){
maxLength=currentLength;
}
}
}
return maxLength;
}
public int longestConsecutive(int[] nums) {
//定义map为num及其所在连续序列的长度
Map<Integer, Integer> map=new HashMap<>();
int left;
int right;
int currentLength;
int maxLength=0;
for(int num : nums){
//不包含num
if(!map.containsKey(num)){
//对于第一次出现的num, num-1出现的范围只能是[num-left, num-1]
left=map.getOrDefault(num-1, 0);
//num+1出现的范围只能是[num+1, num+right]
right=map.getOrDefault(num+1, 0);
currentLength=left+right+1;
if(currentLength>maxLength){
maxLength=currentLength;
}
//旁边的两个数 我已经相告了，这里对num保存的值不重要
map.put(num, currentLength);
//告诉左边的数字我的右边连续子序列长度是curLength（或者说只有他左边的数字需要他）
map.put(num-left, currentLength);
//告诉右边的数字我的左边连续子序列长度是cur_length
map.put(num+right, currentLength);
}
}
return maxLength;
}
}
