LeetCode高频题128. 最长连续序列，经常被互联网大厂面试考到
提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题
题目
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-consecutive-sequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、审题
示例 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
基本上都是o（n）复杂度一遍搞定
最巧妙的方法，就是用set去找那个最小的开头，然后一串撸下去，把长度收集起来，6得很
这个方法啥意思呢？
就是说，你把arr所有元素放入set中
从arr的i=0–N-1遍历一遍
核查每一个元素x
（1）如果x-1在set中，显然x不能做一个最长连续序列的开头，你看看是不是，因为x开头不可能最长啊，x-1还在呢，x-1会那个最长的序列更长
你看看上面的x=2
x-1=1，1在set中，显然2不能作为一个最长连续序列的开头，因为它开头的话，长度3
咋着也没有1开头的长度4长
（2）如果发你发现x-1竟然，没有在set中，x就可以做一个最小的开头
比如
x=1，x-1=0，0不在set中，显然，可能从1开始的序列，是最长的连续序列
这么一搞的话，你也不会多遍历，因为下一次要再开头找得是x=6了，这样x-5不在set中
不过下次x=100，很短的，再撸一条新的序列也没用，干不过4这个长度
okay，思想你应该OK了
撸代码就是控制x能作为开头的情况下，去找，更新最大长度
一遍o（n）遍历问完就搞定
手撕代码：
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return 1;
int N = nums.length;
int max = 1;
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < N; i++) {
set.add(nums[i]);
}
//（1）如果x-1在set中，显然x不能做一个最长连续序列的开头，
// 你看看是不是，因为x开头不可能最长啊，x-1还在呢，x-1会那个最长的序列更长
//（2）如果发你发现x-1竟然，没有在set中，x就可以做一个最小的开头
for(Integer x: nums){
int len = 1;//如果开头OK，就是x自己一个长度
if (!set.contains(x - 1)){
//x就是一个合适的开头
int num = x;//从x开头算
while (set.contains(num + 1)){
len++;//x+1也在，OK连续了
num++;
}
//啥时候断开，OK更新max
max = Math.max(max, len);
}
//统计过的一定不会来了，因此o（n）
}
return max;
}
绝对OK
测试一把：
public static void test(){
int[] arr = {100, 200, 3, 2, 1, 4};
Solution solution = new Solution();
System.out.println(solution.longestConsecutive(arr));
}
public static void main(String[] args) {
test();
}
结果：
LeetCode测试
额，虽然o（n），但是，应该说，set那个地方，加入，包括set的查询，实际上有点费时间了
下面看看还能否提速
还有一个比较中规中矩的办法，用俩哈希表记录每个数x所在的段首，段尾，这样把最长长度更新出来
咋说呢？
俩哈希表mapHead，mapTail
一个记录arr中任意数字x，x做头的这段最长连续子序列的长度是？x做尾部时的这段最长连续子序列的长度是？
比如100, 200, 3, 2, 1, 4，其实4这段做头的话，它最长长度是1，而4做尾的那段连续子序列长度是4
懂？
有了mapH，和mapT
遍历arr中的每一个数x
（0）最开始x来了，直接把x当做单独一段，则x做头长度或者做尾的这段长度自然是1，默认就自己单独做一段呗
（1）然后，立马查询：一定要查一下x-1是不是在mapHead中了？
如果x-1在mapHead中有了，则x的就不能做头，必须从mapHead中删除，同时你还要更新x-1的这段长度
（2）同时查一下x+1是不是在mapTail中了？
如果x+1在mapTail中，则x就不能成尾部，需要删除，更新x+1这段的长度，
这么做就是要保证我们一直更新那个最长连续序列
比如
100, 200, 3, 2, 1, 4
x从左往右遍历，直到x=1时，咱们map都记录了这些：
100,200，各自都是独立成段，长度都是1
3进来独立成首尾
然后2来独立成首尾，查x-1=1没有，不管，但是x+1=3可是有了的，所以2不可能做尾，3也不可能做头，所以x=3做尾部，最长连续子序列长度暂时是2，2做开头，长度也是2
然后1进来独立成首尾，查x-1没有，不管，但是x+1=2可是有了的，所以1不可能做尾，2也不可能做开头，删除，所以x=1做开头的最长连续子序列长度是3
再来一个4，会是啥情况呢？
查x+1=5，没有，不管
查x-1=3，有的，显然4不能做开头了，3也不可能做结尾了，更新长度
4做结尾的最长连续子序列长为4，同时1开头的长也为4
咦？？？？？
你一定纳闷，我咋知道4更新，1也要更新呢？
你咋知道1要更新呢？
难不成是一个一个从4,3，2,1遍历来的？
不，其实这里根据4所在区间的长度去算出来了的
我们会单独整一个函数，去更新mapHead和mapTail
下面定义一波merge函数，带着map，然后preEnd，和curStart
如果preEnd是x-1，则curStart就是x
如果preEnd是x，则curStart就是x+1
当preEnd是x-1，则curStart就是x，一旦调用这个函数，意味着x-1在mapHead中，我curStart=x不能做头了，x-1=preEnd也不能做尾了
所以map中最终要删除他们俩
而新的一段起点是啥呢？preStart实际上是preEnd-mapHead.get(preEnd)+1
就像上面的x=4，preEnd=x-1=3
mapHead.get(preEnd)=3，因此，我们知道真的3所在的这段开头应该是preStart=3-3+1=1
这就是为啥，我来到4这个地方，我知道1那所在段的长度是4，也要更新了，懂了吧？？？
同时，如果preEnd是x，则curStart就是x+1
意味着，x是不能做尾部的，x=1不能做头的，因此我需要更新x的长度，也要知道x+1那段长度所在尾部的下标curEnd是多少？
curEnd=curStart+mapTail.get(curStart)-1；
比如上面的preEnd=x=2时，curStart=x+1=3
mapTail.get(curStart)=1，因此
最后3作为尾时，除了更新2作为开头的长度为2之外
还要更新curEnd=curStart+mapTail.get(curStart)-1；作为尾的长度也是2，他俩是同一段连续子序列
curEnd=3+1-1=3
因此绿色那俩2代表我们是同一段连续子序列，因此要同时更新
长度2怎么来？
len=curEnd-preStart+1
这个过程很复杂，但是事情就是，mapH，mapT记录着x开头的那段最长子序列长度，x结尾的那段最长子序列长度
随着更多数来，拿着preEnd–curStart更新的那些连续子序列开头preStart–curEnd要重新更新长度
过程比较繁杂，但是思想就是这么个思想
手撕代码主要是理解这个更新长度的过程：
//方法1的合并，需要俩map，删除中间点
//x-1作为前一段的结尾，x是当前段的头，合并之后，preStart重新计算，curEnd也从新计算了
public static int mergeMethd1(HashMap<Integer, Integer> mapHead, HashMap<Integer, Integer> mapTail,
int preEnd, int curStart){
int preStart = preEnd - mapTail.get(preEnd) + 1;
int curEnd = curStart + mapHead.get(curStart) - 1;
int len = curEnd - preStart + 1;//更新的总长度
//删除无用的
mapTail.remove(preEnd);
mapHead.remove(curStart);
mapHead.put(preStart, len);//更新现在段的头
mapTail.put(curEnd, len);//更新现在段的尾
return len;
}
有了这个更新mapH和mapT的函数
其实主函数，就是最开始我们说的，一进来x独立成段，长度都是1，立马查x-1是否在mapHead中，立马查x=1是否在mapTail中
查x-1时，preEnd=x-1，curStart=x，合并前面x-1这段，和我x这段
查x+1时，preEnd=x，curStart=x+1，合并前面我x这段和后面x+1这段
更新合并之后，前面那段的起点preStart就是最新起点，后面这段的尾部就是最细结尾curEnd
每一次检查合并，都要把最长长度给max，作为结果
然后手撕代码：
//首先来一个方法1：双map的解法，很简单，能解决问题
//这是最常规的做法，就是map,记录每一个段的开头，极其长度，记录每一个段的结尾，极其所在段的长度
//查x-1和x+1，然后删除中间的那些元素，只保留一头一尾
//合并过程中更新max
public static int longestConsecutiveLen1(int[] arr){
if (arr == null || arr.length == 0) return 0;
HashMap<Integer, Integer> mapHead = new HashMap<>();
HashMap<Integer, Integer> mapTail = new HashMap<>();
int max = 1;
for (int i = 0; i < arr.length; i++) {
//遍历每一个数字
//一进来都是独立成段的
mapHead.put(arr[i], 1);
mapTail.put(arr[i], 1);
//然后查，合并，返回结果，更新max
if (mapTail.containsKey(arr[i] - 1)){
//x-1确实在结尾中有，需要合并这两段
max = Math.max(max, mergeMethd1(mapHead, mapTail, arr[i] - 1, arr[i]));
}
if (mapHead.containsKey(arr[i] + 1)){
//x-1确实在结尾中有，需要合并这两段
max = Math.max(max, mergeMethd1(mapHead, mapTail, arr[i], arr[i] + 1));
}
}
return max;
}
你看主函数的代码，和那个merge的代码，再返回去看我的图
仔细理解这个合并过程
确实复杂，但是速度应该快点
今天我先不验证了，太晚，我回头重新自己手撕代码，然后再来验证
笔试你先写set那个方法
面试的话，可以跟面试官聊一下这个方法
总结
提示：重要经验：
1）set可以控制最小的开头
2）哈希表俩记录最长连续子序列的长度，那个过程复杂，关键就是合并过程
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。