leetcode刷题记录（四十八）——128. 最长连续序列

（一）问题描述

128. 最长连续序列 - 力扣（LeetCode）128. 最长连续序列 - 给定一个未排序的整数数组 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] <= 109https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked给定一个未排序的整数数组 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

 （二）解决思路

这道题目要求找连续序列，同时不要求序列位置连续，即查找数值大小上连续的元素有几个。那么使用哈希结构中的集合（Set）是最合适的：可以去除数组中重复的元素，又能快速找到符合条件的元素。

思路很简单：

• 找到序列的起始元素（即序列当中数值最小的元素）
• 不断找到该序列中的下一个元素（比当前元素大一），每找到一个，序列长度就加一
• 一个数组里可能包含多个序列，比较得到的多个长度取最大，就是当前数组中的最大连续序列长度。

class Solution {public int longestConsecutive(int[] nums) {//将给定数组转换为集合Set<Integer> s=new HashSet<>();for(int n : nums){s.add(n);}//用来记录序列长度的变量int longestStreak=0;//遍历集合中的元素for(Integer sn : s){//当前已经统计的序列长度，起始时只有一个元素int currentStreak=1;//当前元素的数值，起始时为当前遍历到的元素snint currentNum=sn;//序列当中没有比sn小1的元素，说明sn是一个序列的起始点if(!s.contains(sn-1)){   //只要有比sn大一的元素，就说明序列还没有结束，不断找序列中的下一个元素，同时序列长度加一while(s.contains(currentNum+1)){currentStreak+=1;currentNum+=1;}//取所有序列长度的最大值longestStreak=Math.max(longestStreak,currentStreak);}}return longestStreak;}
}

 （三）易错点

        这道题要求时间复杂度为O（n），那么就不能有排序，只要针对数组排序，时间复杂度就会大于O（n）。所以这道题解题的关键是想到找序列的起点，以及怎么找序列的节点。如果不找序列的起点，是没有办法按顺序累加元素的。

        另外也不是循环嵌套，时间复杂度就一定大于O(n)的哈。像这道题里面第二层循环的执行是有条件的，时间复杂度还是O(n)。