leetcode128最长连续序列 golang版

题目描述

题目：给定一个未排序的整数数组 nums 找出数字连续的最长序列，不要求序列 元素在原数组中连续 的长度
请你设计并实现时间复杂度为On的算法解决此问题
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4 。
关键 用哈希表来记录这个字符是否出现过 然后遍历数组 对于每个数字 检查它是否是某个序列的开始,并更新最大长度
做不出来可以先看看题目，实在没思路再往下看看思路

解题思路

1. 可以用一个哈希表存储需要查找的字符串
2. 判断当前数字是否在哈希表中 如果当前数字在哈希表中那么它可能是一个连续的序列的起点，
3. 找到这个起点向后遍历
4. 确定最大长度返回

解题步骤

1. 判断边界条件
2. 创建哈希表存储这个数
3. 将每个数字添加到哈希表中
4. 初始化序列最长的长度、和当前查找的序列长度
5. 遍历这个哈希表中的所有数字找到它的最长序列返回

代码实现

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 := 0
    for num :=  range set {
       // 如果当前数字的前一个字符不在哈希表中 那么当前这个数字就有可能是这个序列的起点
      if !set[num-1] {
           currentNum := num
           currentSteark := 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] 做了什么事

这里说明了 如果当前元素的前一个元素不存在这个哈希表中的话，那么这个元素就可能是这个序列的起点。那么接下来的代码就会从这个数字开始找这个序列。