网络异常，图片无法展示
|
给定一个未排序的整数数组 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
sort
解题思路
本题输入的是一个未排序的数组，但是要找的是数字连续的子序列，所以最直接想到的方式就是进行升序排序，然后根据数字连续的性质获取子序列的长度，最后所有子序列长度的最大值就是要求的结果值。
代码实现
var longestConsecutive = function(nums) { // 对输入数组升序排序 nums.sort((a,b) => a-b) // 初始化最大值为0，当前子序列长度为0，前一个元素值为正无穷 let max = 0,len = 0,pre = Infinity; // 遍历排序后的输入数组 for(let i = 0;i<nums.length;i++){ // 如果当前值 = pre,说明是重复值，跳过循环 if(pre === nums[i]) continue; // 如果当前符合数字连续性质，子序列长度+1 if(pre === nums[i]-1) len++ // 否则，说明前一个子序列结束，尝试更新max,并重置 len = 1 else max = Math.max(max,len),len = 1 // 更新 pre 为当前元素值 pre = nums[i] } // 返回 max 和最后一个子序列长度的最大值 return Math.max(max,len) }; 复制代码
这样的解题思路虽然可以解决问题，但是因为先进行了一次排序，所以并没有达到本题对于时间复杂度 O(n) 的要求。
Set
解题思路
将输入数组转为 Set,遍历 Set,如果在集合中找不到当前元素值-1的元素，则说明当前元素是其所在子序列的第一个元素。
初始化当前子序列长度为1，然后查找是否有值为当前元素值+1的元素，如果可以找到，则长度+1，并继续查找。
当无法找到符合要求的元素，则说明当前子序列结束，尝试用当前子序列长度更新结果值。
当遍历完整个集合，就获取到了最长子序列的长度。
代码实现：
var longestConsecutive = function(nums) { // 根据输入数组创建set const set = new Set(nums); // 初始化结果值为 0 let res = 0; // 遍历 set set.forEach(item => { // 如果 set 没有当前值-1的值，说明当前值是其所在子序列的起始值 if(!set.has(item-1)){ // 初始化 len = 1 let len = 1; // 当可以找到当前值 +1 的值时，子序列长度+1，并更新当前值 while(set.has(item+1)){ len++,item++ } // 尝试用子序列长度更新结果值 res = Math.max(res,len) } }) // 返回结果值 return res; }; 复制代码
至此我们就完成了 leetcode-128-最长连续序列
如有任何问题或建议，欢迎留言讨论！
