题目描述
题目：给定一个未排序的整数数组 nums 找出数字连续的最长序列，不要求序列 元素在原数组中连续 的长度
请你设计并实现时间复杂度为On的算法解决此问题
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4 。
关键 用哈希表来记录这个字符是否出现过 然后遍历数组 对于每个数字 检查它是否是某个序列的开始,并更新最大长度
做不出来可以先看看题目，实在没思路再往下看看思路
解题思路
- 可以用一个哈希表存储需要查找的字符串
- 判断当前数字是否在哈希表中 如果当前数字在哈希表中那么它可能是一个连续的序列的起点，
- 找到这个起点向后遍历
- 确定最大长度返回
解题步骤
- 判断边界条件
- 创建哈希表存储这个数
- 将每个数字添加到哈希表中
- 初始化序列最长的长度、和当前查找的序列长度
- 遍历这个哈希表中的所有数字找到它的最长序列返回
代码实现
func longestConsecutive(nums []int) int {// 1. 左边界判断 做算法 的第一步if len(nums) == 0 {return 0}// 2.初始化哈希表set := make(map[int]bool)// 3.将数据存储到哈希表中for num := range nums {set[num] = true}// 3. 初始化 最长序列maxLength := 0for num := range set {// 如果当前数字的前一个字符不在哈希表中 那么当前这个数字就有可能是这个序列的起点if !set[num-1] {currentNum := numcurrentSteark := 1}for set[currentNum+1] {currentNum++currentSteark++}// 4.找到最大的那个序列长度maxLength := max(maxLength,currentSteark)}}// 5.返回最大值的序列长度return maxLength
}
代码测试
func main() {nums := []int{100, 4, 200, 1, 3, 2}fmt.Println("Longest consecutive sequence length is:", longestConsecutive(nums))
}
测试结果
Q&A
为什么使用哈希表来完成这个算法
1 .使用哈希表 可以最快效率的查到该元素 哈希表的复杂度为0(1)
2. 满足这个题目的时间复杂度On的要求
if !set[num-1] 做了什么事
这里说明了 如果当前元素的前一个元素不存在这个哈希表中的话，那么这个元素就可能是这个序列的起点。那么接下来的代码就会从这个数字开始找这个序列。
