LeetCode 128. 最长连续序列 golang

最新推荐文章于 2024-06-03 06:06:19 发布

hodgeKou

最新推荐文章于 2024-06-03 06:06:19 发布

阅读量508

点赞数

分类专栏： LeetCode

本文链接：https://blog.csdn.net/csdn_kou/article/details/106056879

版权

LeetCode 专栏收录该内容

152 篇文章

订阅专栏

该博客主要介绍了如何使用Golang解决LeetCode中的第128题，即寻找未排序整数数组中的最长连续序列。题目要求在O(n)的时间复杂度内完成，示例中给出的输入数组[100, 4, 200, 1, 3, 2]，其最长连续序列是[1, 2, 3, 4]，长度为4。" 104079445,8686410,接口隔离原则详解与实践,"['设计模式', '软件设计', '接口设计']

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

128. 最长连续序列

【困难】

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

Code


// 解题思路
// 将所有nums中元素录入numMap
// 对每个numMap中元素，检测是否是第一个起始元素，如果不是起始元素，skip；如果是，对该元素循环+1从numMap找到该元素对应的最长currentLength
// longest = max(longest, currentLength)
// 代码
func longestConsecutive(nums []int) int {
	numMap := make(map[int]bool)
	for _, number := range nums {
		numMap[number] = true
	}

	longest := 0
	for k, _ := range numMap {
		if _, prs := numMap[k-1]; prs {
			continue
		}
		currentLength := 1


		for {
			if _, prs1 := numMap[k+1]; !prs1 {
				break
			}
			currentLength++
			k++
		}
		longest = max(longest, currentLength)
	}


	return longest
}

func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}