给定一个未 排序 的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)
。
示例:
输入:[100, 4, 200, 1, 3, 2]
输出: 4
解释:最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
思路
-
连续序列,首先要对传入数组进行 排序
-
连续序列的标志为
s[n] - s[n-1] === 1
,针对这个来进行循环判断
-
定义循环中的最大长度
num
以及最终长度 max
,每次需取 max(num, max)
-
当 s[n] - s[n-1] !== 1 时,及连续序列断开,需重置当前最大长度
-
特殊用例情况:[1,2,2,3]中的连续序列为[1,2,3],长度为3。因此在循环中当s[n] === s[n-1]时候,应跳过
直接上代码
/**
* @param {number[]} nums
* @return {number}
*/
var lOngestConsecutive= function(nums) {
if (!nums.length) return 0;
var sortedNums = nums.sort((a,b) => (a - b));
var i = 1;
var num = 1;
var max = 1;
while(i