NOTES · 学习笔记
最长连续序列:起点判断 + 哈希查询
题目
题目要求时间复杂度为 O(n),所以我们不能排序——排序的时间复杂度是 O(n log n)。那我们用哈希来解决:把数字放进哈希表中,然后遍历每个数字。怎么判断是不是起点?看 num-1 是否存在:如果上一个数字存在,说明当前这个数不是起点。
我们看示例:nums = [100,4,200,1,3,2],哈希表中存着 {100,4,200,1,3,2}。遍历:num=100,检查 99,存在吗?不存在,100 是起点,长度 1。num=4,检查 3,存在,说明 4 不是起点,跳过。
从起点开始找:定义一个 current 表示当前数,不断向后寻找连续数字,length 从 1 开始。也就是如果 num-1 不存在——当前数字是起点,就不断 num+1 查询下去,最后更新最大长度返回。
func longestConsecutive(nums []int) int {
hash := make(map[int]bool) // 定义一个哈希map用来存数字
for _, num := range nums { // 遍历nums中的值
hash[num] = true // 将nums中的值保存在hash中
}
maxLength := 0 // 定义一个最大长度,我们最后要返回最大长度
for num := range hash { // 哈希目前已经存放了nums中的值,我们遍历哈希
if hash[num-1] { // 如果当前数字的前一个数字也存在我们保存的hash中
continue // 跳过,因为它不是我们要找的第一个数
}
current := num // 定义一个变量用来表示现在num的数是哪个
length := 1 // 长度为1,因为当前包含起点数字
for hash[current+1] { // 当前 current 是连续序列的起点,不断寻找后面的数字
current++ // 如果后面的数存在我们就自增
length++
}
if length > maxLength { // 如果现在连续的长度大于最大长度
maxLength = length // 我们更新一下最大长度
}
}
return maxLength
}