给定一个未排序的整数数组 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
方法:哈希表
时间复杂度:O(n)
空间复杂度:O(n)
1 /** 2 * @param {number[]} nums 3 * @return {number} 4 */ 5 var longestConsecutive = function(nums) { 6 let num_set = new Set(); 7 for (const num of nums) { 8 num_set.add(num); 9 } 10 let longestStreak = 0; 11 for (const num of num_set) { 12 if (!num_set.has(num - 1)) { 13 let currentNum = num; 14 let currentStreak = 1; 15 while (num_set.has(currentNum + 1)) { 16 currentNum += 1; 17 currentStreak += 1; 18 } 19 longestStreak = Math.max(longestStreak, currentStreak); 20 } 21 } 22 return longestStreak; 23 }
标签:set,nums,longestStreak,序列,num,let,128,最长 From: https://www.cnblogs.com/icyyyy/p/16877561.html