128. Longest continuous sequence

---

128. The longest continuous sequence

Given an array of unsorted integers nums , Find the longest sequence of consecutive numbers （ Sequence elements are not required to be contiguous in the original array ） The length of .

Please design and implement it with a time complexity of O(n) The algorithm to solve this problem .

Example 1：

Input ：nums = [100,4,200,1,3,2]
Output ：4
explain ： The longest consecutive sequence of numbers is [1, 2, 3, 4]. Its length is 4.

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/longest-consecutive-sequence
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking

Two hash tables
Continuous interval header table + Continuous interval tail table

100 The process of coming
The header table is added (100,1),1 For the length
Tail table addition (100,1)

Join in 3

Join in 4, Check whether there is an interval that can be connected

Check the header table , Find out 3, take 3 And 4 Connect , become (3,2), For from 3 set out , It can be connected 2 An interval of length
View footer , Find out 3, take 3 And 4 Connect , become (4,2), Representative to 4 For the end , It can be connected 2 An interval of length

Each time he counts, he builds his own interval , See if it can't match up with before , See if the back can close ,
After you close it strictly every time , You ask me how long the last continuous interval is , Feel free to find - A watch , hold value Take out the maximum value
When every number comes , The operation of hash table is 0(1)

Code

Versions of two hash tables

	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;
	}

A hash table

	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;
	}