128. 最长连续序列

给一个没排过序的整数数组，找出最长的连续数字串，返回它的长度。连续的意思是数字一个接一个，像 1、2、3、4 这样，中间不能断。数组里可以有重复的数，重复不算两次。题目（出处：力扣 128 题面）给的第一个例子是 [100, 4, 200, 1, 3, 2]，答案是 4，对应 1、2、3、4 这一串。第二个例子是 [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]，答案是 9，从 0 一直连到 8。题目还要求时间复杂度做到 O(n)，这句话我一开始没太当回事，写完才发现它把最顺手的那条路堵死了。

先写最笨的办法

我最先想到的办法特别直接：把所有数放进一个集合，对每个数往后一个一个查，1 在不在，2 在不在，查到断为止，数出来的长度取最大。

def longest_bruteforce(nums):
    s = set(nums)
    best = 0
    for x in nums:
        cur = 1
        while x + cur in s:
            cur += 1
        best = max(best, cur)
    return best

这个写法答案是对的，但慢得离谱。问题出在重复劳动上：1、2、3、4 这条链，从 1 开始数要走 4 步，从 2 开始数又走 3 步，从 3 开始数再走 2 步，同一条链被反反复复数了好几遍。最坏的情况是数组本身就是一串连续数，比如 0 到 19999，那总共要查差不多 2 亿次。我本地跑了一下，0 到 19999 这组数据，这个写法用了 13.4695 秒。答案 20000 是对的，就是等得人难受。

排序那条路

换个思路，先排序，再扫一遍，挨着的两个数差 1 就接着数，差得更多就断开，遇到重复的数跳过。

def longest_naive_sort(nums):
    if not nums:
        return 0
    a = sorted(nums)
    best = cur = 1
    for i in range(1, len(a)):
        if a[i] == a[i - 1]:
            continue
        if a[i] == a[i - 1] + 1:
            cur += 1
        else:
            best = max(best, cur)
            cur = 1
    return max(best, cur)

这个办法没有重复劳动，写起来也顺，唯一的毛病是排序本身要 O(n log n)，题目要的 O(n) 达不到。n=100000 的随机数（数值 0 到 99999，种子 7）上它用了 0.0453 秒，答案 26。比上面那个逐个查的快得多，但还是没满足题目的要求。而且排序这一步跟题目真正想考的东西没什么关系，属于绕过去了。

只从链头开始数

省事的观察是，一条连续链里，只有一个数值得当起点：链里最小的那个。1、2、3、4 这条链，起点只能是 1，因为 1 的前一个数 0 不在数组里，而 2、3、4 的前一个数都在。换句话说，一个数如果它的前一个数也在数组里，那它一定不是某条链的开头，从它开始数出来的链，肯定是另一条更长的链的后半截，长度超不过那条链。跳过它，什么都不会丢。

所以做法是：先把所有数放进集合，然后只对“前一个数不在集合里”的数往后数，数到断为止，取最长的一条。每个数最多被数到一次，因为它只属于一条链，而这条链只会从它的链头开始数一遍。再加上每个数一次“前一个数在不在”的查找，总共就是 O(n) 次集合操作。集合查找平均 O(1)，整个做法就是 O(n) 时间，额外空间 O(n)，用来放这个集合。

拿官方第一个例子走一遍：数组是 [100, 4, 200, 1, 3, 2]，集合里是 1、2、3、4、100、200 这六个数。1 的前一个数 0 不在集合里，是链头，往后数出 1、2、3、4，长度 4。4 的前一个数 3 在，直接跳过。3 和 2 也一样，都跳过。100 的前一个数 99 不在，是链头，数出 100 自己，长度 1。200 同理，长度 1。三个链头数完，答案就是 4。整个过程集合查找约 12 次。第二个例子 [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] 更干脆，只有一个链头 0，一口气数出 0 到 8，长度 9。

正式代码

def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:  # 链头：前一个数不在集合里
            cur = 1
            while x + cur in s:
                cur += 1
            best = max(best, cur)
    return best

这里有个小地方：循环写的是 for x in s，不是 for x in nums。数组里有重复的数，for x in nums 会让同一个数被当成链头检查好几次，虽然结果一样，但白做了重复的查找。换成在集合上循环，每个不同的数只检查一次。

空数组要单独想一下：集合是空的，循环一次也不跑，best 保持 0，返回 0。单个数的数组，[5] 这种，5 是链头，数出长度 1。负数也没什么特别的，[-3, -2, -1, 0] 的链头是 -3，数出来长度 4，跟正数走的是同一套逻辑。

我拿什么验的

官方的两个例子都过了：[100, 4, 200, 1, 3, 2] 得 4，[0, 3, 7, 2, 5, 8, 4, 6, 0, 1] 得 9。然后我写了 3000 组随机数据（种子 20261109，长度 0 到 30，数值 -20 到 20），把正式解法的结果和排序解法逐个对，失配是 0 组。边界也顺手测了：[] 是 0，[1, 1, 1] 是 1，[1, 3, 5, 7] 这种谁也不挨着谁的是 1，[10, 5, 12, 3, 11] 是 3，对应 10、11、12。

速度上也对得上。n=100000 的随机数（数值 0 到 99999，种子 7），正式解法 0.0184 秒，排序解法 0.0453 秒，答案都是 26。0 到 19999 那组连续数，逐个查的写法 13.4695 秒，正式解法 0.0029 秒，差了四千多倍。慢的那个思路没错，就是同一条链数了太多次；快的这个也没用什么新招，就是每条链只从链头数一遍。

回头看，代码只有十来行，难处在敢不敢跳过那些没数过的起点。逐个查的写法图个安心，每个数都数一遍；正式解法先想清楚一件事，从非链头开始数的链一定是某条链的后半截，这才敢跳过。想通这一点，O(n) 就是顺手的事。

对照 doocs/leetcode 的 0128 题解这一步后来补上了：它一共两个方法，都是哈希表。方法一是边扫边删、另用一张表记每段长度；方法二是只从链头数，也就是 x-1 不在集合里才往后数，与本文正式解法结构相同。标签里虽有「并查集」，正文并没有并查集解法。对下来没有遗漏的情形。