golang力扣leetcode 128. 最长连续序列

128. 最长连续序列

128. 最长连续序列

128. 最长连续序列

题解

题目要求在一个数组中找出一个数字最长连续序列,还要是On的复杂度
首先把所有数字存在map里面,然后遍历map,此时要对current进行判断,如果hashmap[current-1]存在,那就跳过这次循环,因为我们要去找最小的一个数,如果不存在,这么那个数字必定是某个连续序列中首位数字,这个时候去计数hashmap[current+1]有几个,即可。外层循环需要 O(n)的时间复杂度,只有当一个数是连续序列的第一个数的情况下才会进入内层循环,然后在内层循环中匹配连续序列中的数,因此数组中的每个数只会进入内层循环一次。根据上述分析可知,总时间复杂度为 O(n),符合题目要求。

代码

func longestConsecutive(nums []int) int {
	hashmap := make(map[int]bool)
	for _, i := range nums {
		hashmap[i] = true
	}
	result := 0
	for current := range hashmap {
		if !hashmap[current-1] { //不存在比current小的数
			current := current
			cnt := 1
			for hashmap[current+1] {
				current++
				cnt++
			}
			if result < cnt {
				result = cnt
			}
		}
	}
	return result
}
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

cheems~

你的鼓励将是我创作的最大动力

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付:¥1
获取中
扫码支付

您的余额不足,请更换扫码支付或充值

打赏作者

实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值