LeetCode #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

示例 3：

输入：nums = [1,0,1,2] 输出：3

提示：

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

分析

问题要求的是找到最长的数学上的连续整数序列，序列元素在原数组中不一定连续。

1. 排序

我们往往在求解连续序列问题上尝试排序的做法，原因主要有以下几点：

• 直观：排序后，连续的数字会自然相邻
• 便捷：遍历排序后的数组，检查每个数字是否和前一个数字连续（nums[i] == nums[i-1] + 1），就能快速找到最长连续序列。
• 经验：排序常被用于解决“相邻元素”问题

如果允许排序，那我们的思路很简单，就是排序，然后逐个遍历自己的上一位而已。

def sort_solution(nums):
    nums_sorted = sorted(nums)
    max_length = 1
    current_length = 1
    for i in range(1, len(nums_sorted)):
        if nums_sorted[i] == nums_sorted[i-1] + 1:
            current_length += 1
        else:
            max_length = max(max_length, current_length)
            current_length = 1
    return max_length

但是排序是$O(n\log{n})$的，并不符合题目的要求，题目要求我们设计$O(n)$的算法，也就是不允许我们使用排序，换句话说，排序是不必要的，它完成了远超我们所需的任务量。

那我们需要什么呢？根本上讲，就是如何判断某个数是否位于一个连续序列当中，并且以更快的速度判断。

2. 连续序列的判定

怎么判断x是不是位于一个连续序列中呢？事实上，我们可以换一换思路：对于x自己而言，可以认为是一个以自己为开始，以自己为结束的连续序列，然后检查自己是否有前缀x-1即可，如果有，说明自己不是真正的起始点，放弃序列构建。如果没有，那么自己就是真正的起始点。那么x+1呢？同样的，假如我们后面看到了x+1，也检查x+1的前缀。这样对每个x的操作都会统一起来，方便编写代码。

所以我们的问题又变成了：前缀元素是否存在？

3. 存在与否的命题

元素存在性问题是算法中的经典问题，我们的优选策略是建立集合来查找，这个策略基于一个基本原理：并查集时间复杂度为$O(1)$。这个原理十分重要，它解决了查找问题的时间复杂度过高的问题，提出了更低成本的搜索方法。

本例中，搜索前缀便可以采用这个思路，我们选择对整个序列建立集合，实现常数级别的前缀搜索。

def longestConsecutive(self, nums: List[int]) -> int:
    num_set = set(nums)

    for num in num_set:
        if num-1 not in num_set:
            curr = num
            count = 1

            while curr+1 in num_set:
                curr += 1
                count += 1

            longest = max(longest, count)

    return longest