---

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-consecutive-sequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

两个哈希表
连续区间头表+连续区间尾表

100来到的过程
头表加入(100,1),1为长度
尾表加入(100,1)

加入3

加入4,查看有没有能连接的区间

查看头表,发现3,将3与4连起来,变成(3,2),代表从3出发,可以连成2个长度的区间
查看尾表,发现3,将3与4连起来,变成(4,2),代表以4为结尾,可以连成2个长度的区间

每个数来的时候都自己建出自己的区间，看看跟之前都不能合，看看后面能不能合，
你每次都严严格格的合完之后，你问我最后有多长的连续区间，你随便找-张表，把value最大值拿出来
每一个数来到的时候，对于哈希表的操作都是0(1)

代码

两个哈希表的版本

	public static int longestConsecutive2(int[] nums) {
    
		HashMap<Integer, Integer> headMap = new HashMap<Integer, Integer>();
		HashMap<Integer, Integer> tailMap = new HashMap<Integer, Integer>();
		HashSet<Integer> visited = new HashSet<>();
		for (int num : nums) {
    
			if (!visited.contains(num)) {
    
				visited.add(num);
				headMap.put(num, 1);
				tailMap.put(num, 1);
				if (tailMap.containsKey(num - 1)) {
    
					int preLen = tailMap.get(num - 1);
					int preHead = num - preLen;
					headMap.put(preHead, preLen + 1);
					tailMap.put(num, preLen + 1);
					headMap.remove(num);
					tailMap.remove(num - 1);
				}
				if (headMap.containsKey(num + 1)) {
    
					int preLen = tailMap.get(num);
					int preHead = num - preLen + 1;
					int postLen = headMap.get(num + 1);
					int postTail = num + postLen;
					headMap.put(preHead, preLen + postLen);
					tailMap.put(postTail, preLen + postLen);
					headMap.remove(num + 1);
					tailMap.remove(num);
				}
			}
		}
		int ans = 0;
		for (int len : headMap.values()) {
    
			ans = Math.max(ans, len);
		}
		return ans;
	}

一个哈希表

	public static int longestConsecutive(int[] nums) {
    
		HashMap<Integer, Integer> map = new HashMap<>();
		int len = 0;
		for (int num : nums) {
    
			if (!map.containsKey(num)) {
    
				map.put(num, 1);
				int preLen = map.containsKey(num - 1) ? map.get(num - 1) : 0;
				int posLen = map.containsKey(num + 1) ? map.get(num + 1) : 0;
				int all = preLen + posLen + 1;
				map.put(num - preLen, all);
				map.put(num + posLen, all);
				len = Math.max(len, all);
			}
		}
		return len;
	}