给定一个未排序的整数数组
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
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109
思路：
可参考 官方题解思路
- 借助map这一数据结构来存储和去重nums数组元素
- 遍历map，判断当前遍历到的num是否可以作为某个连续序列的首元素，即借助map判断是否还有比当前num还小的元素
- 如果map中没有比当前num还小的元素，那么该元素就可以作为某个连续序列的首元素。我们继续寻找以该num为首元素的后继连续序列，即判断：num+1，num+2，...，num+n是否存在，这一过程中顺便记录这个连续序列的长度length。
- 如果map中有比当前num还小的元素，那么该元素就不可以作为某个连续序列的首元素，我们直接跳过即可，不予理会。
时间复杂度：O(n)，其中 n 为数组的长度。虽然存在双层for循环，但是内层for循环实际上已经continue 跳过了很多 “当前num不能作为首元素的连续序列” 了。
空间复杂度：O(n)，哈希表存储数组中所有的数需要 O(n) 的空间
// 可参考官方题解思路：https://leetcode.cn/problems/longest-consecutive-sequence/solutions/276931/zui-chang-lian-xu-xu-lie-by-leetcode-solution/?languageTags=golangfunclongestConsecutive(nums []int) int { maxLength, m :=0, make(map[int]struct{}) fori :=0; i<len(nums); i++ { m[nums[i]] =struct{}{} } fornum, _ :=rangem { // 不存在比当前num还小的数，说明当前num已经是某个连续序列的首元素了if_, ok :=m[num-1]; !ok { // 继续找以当前num为首的连续序列，并记录连续序列的长度j, length :=1, 1for { if_, ok :=m[num+j]; ok { length++j++ } else { break } } ifmaxLength<length { maxLength=length } // else: 存在比当前num还小的数，说明当前num并不是某个连续序列的首元素，直接跳过 } } returnmaxLength} // func longestConsecutive(nums []int) int {// maxLength, m := 0, make(map[int]struct{})// for i := 0; i < len(nums); i++ {// m[nums[i]] = struct{}{}// }// for num, _ := range m {// // 存在比当前num还小的数，说明当前num并不是某个连续序列的首元素，跳过，继续找比它更小的首元素// if _, ok := m[num-1]; ok {// continue// }// // 已经找到某个连续序列的首元素了// j, length := 1, 1// for {// if _, ok := m[num+j]; ok {// length++// j++// } else {// break// }// }// if maxLength < length {// maxLength = length// }// }// return maxLength// }// // 超时：由于第二个for循环是对nums数组的每个num去重复寻找其后继元素，并未证明当前num可以作为某个连续序列的首元素（即当前num已经是某个连续序列中最小的一个）。// // 借助map判断，如果当前num不是某个连续序列的首元素，直接跳过即可，无需重复判断// func longestConsecutive(nums []int) int {// res, m := 0, make(map[int]struct{})// for i := 0; i < len(nums); i++ {// m[nums[i]] = struct{}{}// }// for i := 0; i < len(nums); i++ {// j, length := 1, 1// for {// if _, ok := m[nums[i]+j]; ok {// length++// j++// } else {// break// }// }// if res < length {// res = length// }// }// return res// }
