1
2
3
4
5
6
7
8
|
func main() {
nums := []int{100, 4, 200, 1, 3, 2}
r := longestConsecutive(nums)
fmt.Println(r)
}
func longestConsecutive(nums []int) int {
// ......
}
|
标签前后需要加上%才能支持markdown。
本题要求时间复杂度为O(n)。
自己的一些思考：
自己的思路1：开辟容量为 maxVal-minVal+1 的数组，将每个位置出现的次数记录下来，然后统计最长的连续序列。
这样写存在的问题是，num 可能是负数，就不好使用数组的下标来表示 num 了。
自己的思路2：从大到小，使用 map 记录当前数值连续的数量。
这里有一种 map 和动态规划相结合的思想。
但这样也存在问题：元素出现的顺序不是从大到小的，元素是可以交换顺序的。
参考答案的方法：既然元素之间的顺序不重要，那么我们就可以直接将所有的元素存入 set（numSet）中，
遍历数组，如果 num-1 不在 numSet 集合中，那么就可以从 num 开始往右搜索。（这里还是比较巧妙的）
如果 num+1 在 numSet 集合中，则当前连续的长度加 1（循环这个过程，获得最大的长度）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
func longestConsecutive(nums []int) int {
numSet := map[int]bool{}
for _, num := range nums {
numSet[num] = true
}
maxLen := 0
for num := range numSet {
if !numSet[num-1] {
curNum := num
curLen := 1
for numSet[curNum+1] { // 一直找从num开始的所有连续数字
curNum++
curLen++
}
if maxLen < curLen {
maxLen = curLen
}
}
}
return maxLen
}
|
