题目
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
输入： nums = [100,4,200,1,3,2] 输出： 4 解释： 最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
题目解析
思路一
我们已知数字必须是连起来的，间隔必须是1，最长连起来的数字有多长？把这个长度返回。所以我们先从数组里面取出一个树，n判断n-1是否存在，如果存在，接着判断n-2，直到n-x 不存在，这时候，就到了数组的最前面，这个时候在从x到n这个区间，就是前面最长的数字长度，在接着去判断n+1是否存在，如果存在，继续判断n+2 是否存在，如果n+2存在，在判断n+ m 是否存在，如果不存在就证明走到了数组的最后一位，此时，从n到m这个区间就是后面部分的最长数字长度
/** * @param {number[]} nums * @return {number} */ var longestConsecutive = function (nums) { let num_set = new Set(); for (num of nums) { num_set.add(num); } let longestStreak = 0; for (num of nums) { if (!num_set.has(num - 1)) { let currentNum = num; let currentStreak = 1; while (num_set.has(currentNum + 1)) { currentNum += 1; currentStreak += 1; } longestStreak = Math.max(longestStreak, currentStreak); / } } return longestStreak; };
思路二
我们先对数组进行排序，去重，然后再使用滑动窗口，end指针向右扩大数组范围，直到数组末尾，start指针默认不动，当新加入的end让窗口内无法形成满足条件的数组时，start置为end位置，最后在滑动窗口遍历过程中，窗口的最大长度即为所求最长连续子序列的值
/** * @param {number[]} nums * @return {number} */ var longestConsecutive = function(nums) { let maxLen = 0; nums = nums.sort((a,b) => a - b); nums = Array.from(new Set(nums)); let start = 0, end = 0; while(end < nums.length){ let cur = nums[end]; if(end - start > 0){ let prev = nums[end - 1]; if(prev !== nums[end] - 1){ start = end; } } maxLen = Math.max(end - start + 1, maxLen); ++end; } return maxLen; };
