题目
给定一个未排序的整数数组 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
解析
问题需要被分解为几个子问题:
如何确定一个数是连续序列的起点?
如何高效地扩展连续序列?
如何跟踪和更新最长序列的长度?
解题思路:
用哈希表查找这个数前面一个数是否存在,即num-1在序列中是否存在。存在那这个数肯定不是开头,直接跳过。
因此只需要对每个开头的数进行循环,直到这个序列不再连续。 以题解中的序列举例:
[100,4,200,1,3,4,2]
去重后的哈希序列为:
[100,4,200,1,3,2]
按照上面逻辑进行判断:
元素100是开头,因为没有99,且以100开头的序列长度为1
元素4不是开头,因为有3存在,过,
元素200是开头,因为没有199,且以200开头的序列长度为1
元素1是开头,因为没有0,且以1开头的序列长度为4,因为依次累加,2,3,4都存在。
元素3不是开头,因为2存在,过,
元素2不是开头,因为1存在,过。
代码
func longestConsecutive(nums []int) int {
numSet := map[int]bool{}
for _, num := range nums {
numSet[num] = true
}
longestStreak := 0
for num := range numSet {
if !numSet[num-1] {
currentNum := num
currentStreak := 1
for numSet[currentNum+1] {
currentNum++
currentStreak++
}
if longestStreak < currentStreak {
longestStreak = currentStreak
}
}
}
return longestStreak
}
标签:200,numSet,nums,序列,num,开头,128,解析,leetcode
From: https://blog.csdn.net/shulu/article/details/141681939