Longest Consecutive Sequence
你会得到一个顺序不固定的整数数组 nums。连续序列是一组值 x、x+1、x+2 等，这些值都出现在 nums 中。返回最长连续序列的长度。重复出现的值只计一次。
函数
- numsinteger-array
- 整数，顺序不限，可以重复
- 返回值integer
- nums 中连续出现的值构成的最长连续段的长度
约束条件
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- 值可以重复。数组中的位置不重要，重要的是其中包含哪些值。
示例
- 输入
- nums = [40, 4, 39, 1, 3, 2, 41]
- 输出
- 4
- 解释
1、2、3和4都存在，构成了长度为 4 的连续序列，尽管它们分散在数组中。另一段连续序列从39到41，只有 3 个值。
- 输入
- nums = [7, 3, 7, 5, 6, 5]
- 输出
- 3
- 解释
5、6和7组成一个长度为 3 的连续序列。第二个7和第二个5不会增加任何内容，而3无法加入，因为缺少4。
- 输入
- nums = [10, 30, 20]
- 输出
- 1
- 解释
- 没有两个值相差 1，所以每段连续序列都只包含一个值，答案是 1。
进阶
假设值一个接一个地到来，每收到一个值后，你都必须报告目前为止最长的连续段。你能否在每个值的平均处理时间为 O(1) 的情况下，随时更新答案？
提示
逐个打开提示，每个都会多透露一点。
把每个值都作为序列的起始数字，然后逐渐递增。你会反复提出哪个问题？在数组中搜索时，每次得到答案要付出什么代价？
问题是“
x+1是否在数组中？”。哈希集合通常可以在常数时间内回答这个问题，还能去掉重复项。只从这样的值开始计数：它的
x-1不在集合中。从这里开始，依次检查x+1、x+2等值，只要它们在集合中就继续，并保留最长的一段。这样，每个值都只会被一段连续序列遍历一次。
题解
一次运行中的值可以位于数组中的任何位置。排序可以在 O(n log n) 时间内将它们排列整齐。哈希集合可以在 O(1) 时间内回答“这里有 x+1 吗？”，而且如果只从缺少 x-1 的值开始计数，每个值只会被遍历一次：总共需要 O(n) 时间。
通过搜索数组，从每个值开始递增
结果正确，但无法在最大的测试中运行完毕
思路
把每个值都视为一段连续序列可能的起点。从 x 开始，在数组中查找 x+1，然后查找 x+2，直到找不到某个值，并记录最长的长度。每段连续序列在 nums 中都有一个最小值，循环会从这个值开始遍历整段序列。
每次查找最多读取 n 个值，而且长序列中的每个值都会再次遍历这段序列。对于由 10^4 个值组成的一段乱序序列，这些遍历大约需要 n²/2 = 5 × 10^7 步，每步平均扫描数组的一半：大约需要 2.5 × 10^11 次比较。
算法
- 将
best设为 0。 - 对于
nums中的每个值start，将current设为start，并将length设为 1。 - 当扫描
nums找到current+1时，将current和length都加 1。 - 如果
length更大，就将它存入best。 - 返回
best。
def longestConsecutive(nums):
best = 0
for start in nums:
current = start
length = 1
# "in" on a list reads it from the front until it finds the value.
while current + 1 in nums:
current += 1
length += 1
best = max(best, length)
return best排序后统计连续段
思路
排序会将每段连续序列中的值放到一起：[40, 4, 39, 1, 3, 2, 41] 会变成 [1, 2, 3, 4, 39, 40, 41]，然后从左到右读出这些序列。
遍历排序后的值，并记录当前序列的长度。如果某个值比前一个值大 1，就将它加入当前序列。重复的值既不会延长序列，也不会结束序列，因此跳过它。其他值都会开始一个长度为 1 的新序列。
排序的时间复杂度为 O(n log n)，遍历的时间复杂度为 O(n)。原地排序不需要额外的数组；对副本进行排序的语言会使用 O(n) 的内存。
算法
- 按升序对
nums排序。 - 将
best和run设为 1，因为数组永远不会为空。 - 对从 1 开始的每个索引
i，如果nums[i]等于nums[i-1]，则跳过它。 - 如果
nums[i]等于nums[i-1]+1，则将run加 1；否则将run设为 1。如果run更大，就将它存入best。 - 返回
best。
def longestConsecutive(nums):
nums.sort()
best = 1
run = 1
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
continue # a repeat neither extends nor breaks the run
if nums[i] == nums[i - 1] + 1:
run += 1
else:
run = 1
best = max(best, run)
return best哈希集合，只从每次运行开始时计数
思路
对于哈希集合中的每个值，检查其是否存在的平均时间复杂度为 O(1)，重复值会合并为一个条目。
从每个值开始遍历仍会重复工作：在序列 1, 2, 3, 4 中，从 1 开始要走 3 步，从 2 开始要走 2 步，从 3 开始要走 1 步。因此，只从连续序列的第一个值开始遍历，也就是只从 x-1 不存在的值 x 开始遍历。在示例 1 中，只有 1 和 39 符合条件，分别形成长度为 4 和 3 的连续序列。
每个值都属于一个连续序列，并且只会在该序列的遍历中被经过，因此所有遍历加起来最多需要 n 步。每个值检查一次，总时间复杂度为 O(n)，集合占用的空间复杂度为 O(n)。
算法
- 将
nums中的每个值放入哈希集合values，并将best设为 0。 - 遍历集合中的每个值
x，如果集合中有x-1，就跳过它：它不是连续序列的第一个值。 - 否则，将
end设为x，只要集合中有end+1，就将end加 1。 - 如果
end-x+1更大，就将其存入best。 - 返回
best。
def longestConsecutive(nums):
values = set(nums)
best = 0
for value in values:
# Only a value with no left neighbour starts a run.
if value - 1 in values:
continue
end = value
while end + 1 in values:
end += 1
best = max(best, end - value + 1)
return best
易错点和边界情况
- 排序后把重复值当作间隔或一步。对于
[1, 2, 2, 3]，在第二个2处重置连续序列，结果是 2；把它计为一步，结果是 4。正确答案是 3。 - 在排序遍历中将
best初始设为 0，并且只在循环内更新它。这样，只有一个值的数组会返回 0，而不是 1。 - 从集合中的每个值开始遍历，而不是只从连续序列的起点开始。这样，长度为
10^4的连续序列需要执行5 × 10^7步。 - 遍历
nums，而不是集合。如果一个长度为 2,500 的连续序列的第一个值出现了 2,000 次，就会遍历这个序列 2,000 次。 - 按值作为数组索引。值的范围达到
±10^9，因此需要2 × 10^9个条目。
常见问题3
最长连续序列的时间复杂度是多少？
哈希集合答案的平均运行时间为 O(n)，额外空间复杂度为 O(n)。排序并统计连续序列需要 O(n log n) 时间。对于每个下一个值，如果不使用集合而是在数组中搜索，最多需要 O(n³) 时间。
你能在不使用额外内存的情况下解决最长连续序列问题吗？
可以，如果你可以重新排列输入：原地排序，并在一次遍历中统计连续段，跳过重复项。这样只需要 O(1) 的额外内存，但需要 O(n log n) 的时间。O(n) 的答案需要使用哈希集合。
并查集能解决最长连续序列问题吗？
是的。将每个不同的值作为一个集合处理，只要 x 和 x+1 都存在，就将它们合并，并返回最大集合的大小。它的运行时间接近 O(n)，但需要一个值到索引的映射、父链接和集合大小，而哈希集合遍历只需要一个集合。
def longestConsecutive(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [40, 4, 39, 1, 3, 2, 41]
预期输出
4