0128.最长连续序列

看到这个题目的第一眼想到的自然是排序算法，直接排序遍历，但是复杂度达到了o(nlogn)，不符合题目所要求的o(n)。

对于n复杂度的算法，我第一个想到的是使用哈希map，直接遍历一遍数组，对于每个数字，查找当前数字的「前驱连续长度」（即num-1 所在序列的长度）和后继长度。

如果当前数字未被计算过（这是由于可能出现重复数字），那么就可以合并前后续列长度，并且更新左右边界长度。

看到这里大家可能会有疑问，为什么只需要更新左右边界长度呢？

这是由于每次遇到新的数字时，只有边界的数字会参与计算，中间数字对应哈希值不会被使用到，所以无需更新，且一定小于边界值，不会影响答案。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int ans = 0;
        unordered_map<int, int> map;
        for (int& num : nums) {
            // 1. 查找当前数字的「前驱连续长度」：num-1 所在序列的长度
            int prev = map.find(num - 1) == map.end() ? 0 : map[num - 1];
            // 2. 查找当前数字的「后继连续长度」：num+1 所在序列的长度
            int suf = map.find(num + 1) == map.end() ? 0 : map[num + 1];
            // 3. 仅当数字未被处理过时（避免重复计算）
            if (map.find(num) == map.end()) {
                // 4. 合并前后序列：当前数字的序列长度 = 前驱 + 后继 + 自身（1）
                map[num] += prev + suf + 1;
                // 5. 更新序列「左边界」的长度（关键！）
                map[num - prev] = map[num];
                // 6. 更新序列「右边界」的长度（关键！）
                map[num + suf] = map[num];
				ans = max(ans,map[num]);
            }
        }
        return ans;
    }
};

‍

接下来如果要理解如何从第一个哈希表（记录长度）的算法，转化为题解的哈希集合（找连续序列起点）的算法，核心是换一种思路解决「最长连续序列」问题—— 从「合并序列」转向「找序列起点并统计长度」。

第一个算法的核心是「动态合并」：遍历每个数字时，合并其前后的连续序列，并用哈希表记录序列长度（仅更新边界）。但这个思路有两个「不直观」的点：

1. 需要处理「重复数字」（map.find(num) == map.end()）；
2. 要维护「序列边界的长度」，逻辑上需要理解「为什么只更新边界」；

我们可以思考：有没有更直接的方式？——既然是「连续序列」，那每个序列都有唯一的「起点」（即没有前驱数 ​x-1​​ 的数），只要找到所有起点，再逐个统计以该起点开头的连续序列长度即可。这就是第二个算法的核心思路，大部分是这种思路，就不过多赘述了。

‍