128. 最长连续序列 #
链接 #
题目 #
给定一个未排序的整数数组 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
解答 #
解题思路如下：
- 创建一个集合（Set）：首先，将数组中的所有数字添加到一个集合中。这样做是为了能够在 O(1) 的时间内判断一个数字是否存在于数组中。
- 遍历数组中的每个数字：对于数组中的每个数字，如果它在集合中存在，那么从该数字开始，尝试找到最长的连续序列。
- 寻找连续序列：从当前数字开始，分别尝试找到它的前一个和后一个数字。如果找到，就将其从集合中移除，并继续寻找。这样可以确保每个数字只被访问一次。
- 更新最长序列长度：在寻找每个数字的连续序列时，记录下序列的长度，并与当前已知的最长长度进行比较，更新最长长度。
- 返回结果：遍历完所有数字后，返回最长连续序列的长度。
def longest_consecutive(nums):
if not nums:
return 0
# Step 1: Create a set of numbers for O(1) look-up
num_set = set(nums)
longest_streak = 0
# Step 2: Iterate through the numbers
for num in nums:
# Skip if the number is already visited
if num - 1 not in num_set:
current_num = num
current_streak = 1
# Step 3: Find the sequence
while current_num + 1 in num_set:
current_num += 1
current_streak += 1
# Step 4: Update the longest streak
longest_streak = max(longest_streak, current_streak)
return longest_streak