128. 最长连续序列

题目描述

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

解题

为了设计一个时间复杂度为 O(n) 的算法来解决这个问题，我们可以利用哈希表（Set）的特性。以下是解决方案的详细步骤：

1. 初始化一个哈希表： 将数组中的所有元素插入到一个哈希表中。这样可以实现 O(1) 时间复杂度的查找操作。
2. 遍历数组： 对于每个元素，检查它是否是一个序列的开始（即它的前一个数字不在哈希表中）。
3. 扩展序列： 如果当前数字是序列的开始，则从当前数字开始，向上查找连续的数字，并计算序列的长度。
4. 记录最长序列： 在遍历的过程中，保持更新记录最长序列的长度。

以下是实现这个算法的 Swift 代码：

func longestConsecutive(_ nums: [Int]) -> Int {guard !nums.isEmpty else {return 0}var numSet = Set(nums)var longestStreak = 0for num in nums {// 只考虑序列的开始if !numSet.contains(num - 1) {var currentNum = numvar currentStreak = 1while numSet.contains(currentNum + 1) {currentNum += 1currentStreak += 1}longestStreak = max(longestStreak, currentStreak)}}return longestStreak
}

代码解释

1. 初始化：

   var numSet = Set(nums)
   var longestStreak = 0
   

   将数组元素插入到哈希表 numSet 中，并初始化 longestStreak 记录最长序列的长度。

2. 遍历数组：

   for num in nums {// 只考虑序列的开始if !numSet.contains(num - 1) {var currentNum = numvar currentStreak = 1while numSet.contains(currentNum + 1) {currentNum += 1currentStreak += 1}longestStreak = max(longestStreak, currentStreak)}
   }
   

   对于每个数字，检查它是否是一个序列的开始（即 num - 1 不在哈希表中）。如果是序列的开始，则从当前数字开始，向上查找连续的数字，并计算序列的长度。同时更新 longestStreak。

3. 返回结果：

   return longestStreak
   

   返回最长的序列长度。

这种方法确保每个元素最多被访问两次（一次在 for 循环中，一次在 while 循环中），因此时间复杂度为 O(n)。