【力扣热题100】哈希——最长连续序列
题目
给定一个未排序的整数数组 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
示例 3：
输入：nums = [1,0,1,2]
输出：3
链接：[https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked )
思路
思路一
先排序，然后找最长序列。时间复杂度不符合要求
思路二
时间复杂度为 O(n) 的算法解决此问题。那么只能从头到尾遍历一遍，对于遍历过的数字，要有记忆功能，从记忆中查询的时间复杂度要是 O(1) 。因此，遍历过的数字放到Map里面，Map的key是遍历过的数字，value就是这个数字对应的最长连续序列。
对于每个数字temp，查看比他小1的temp-1是否存在Map里面：如果存在，则value为map.get(temp-1)+1；如果不存在，则循环查看数组里面是否存在temp-1，存在则length++，一直到不再存在为止，那么temp的value就是length。
那这样有两个问题：
- 查看数组里面是否存在
temp-1的操作时间复杂度需要是O(1)，因此一上来遍历一遍数组，将元素放到set当中，判断temp-1是否在set中，从而实现时间复杂度O(1)。 - 如果数组是
[9,8,7,6,5,4,3,2,1]，那么9的时候会全部遍历一遍放到Map当中{9:9}。8的时候又会遍历一遍放到Map当中{9:9,8:8}。时间复杂度为O(n²)或者是O(nm)，m是最长序列的值。但实际上87654321均不需要遍历。因此，对于每个数字temp，先判断temp+1是否存在set当中，如果存在，那么temp+1的序列长度一定大于temp的序列长度，对于temp直接跳过就好。
基于第二个问题，思路当中比他小1的temp-1是否存在Map里面的判断永远为否。因为在检查temp-1时，发现temp在set里，跳过，没有放到map里面。
因此，最后的思路是把数组元素全部放到set当中。对于每个数字temp，查看比他大1的temp+1是否存在set里面：如果存在，则跳过；如果不存在，则循环查看set里面是否存在temp-1，存在则length++，一直到不再存在为止，那么temp的value就是length。
题解
class Solution {public int longestConsecutive(int[] nums) {Set<Integer> set = new HashSet<>();for (int i = 0; i < nums.length; i++) {set.add(nums[i]);}Map<Integer, Integer> map = new HashMap<>();int max = 0;for (Integer temp:set) {// 先判断temp+1是否存在set当中，如果存在，直接跳过if (set.contains(temp+1)) {continue;}// 不存在，则循环查看set里面是否存在temp-1int length = 1;int t = temp-1;while (set.contains(t)) {length++;t--;}max = Math.max(max, length);map.put(temp, length);}return max;}
}