📏 128.最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路

基本思想

为了求出最长的连续子序列的长度，需要不断的将游离的子序列进行合并，这是一个核心的观点，为了合并游离的子序列，就需要在遍历到一个数时，将左右的可能存在的子序列进行合并

最简单的办法就是对数据进行排序，然后自然就合并了，但是题目要求时间复杂度，故不能合并，所以我们使用unordered_map来存储每一个连续子序列中左右端点以及其子序列的长度，例如[1,2,3,4]这个子序列，就只用存储umap[1]=4,umap[4]=4,中间的元素不用管

之所以只用存储端点的值，是因为一旦再新来一个元素，可以将两边游离的子序列合并，只需要读取这两个子序列端点的值就能知道子序列的长度，例如两个子序列[1,2,3,4]和[6,7,8]，此时元素5到达，可以将这两个子序列合并成[1,2,3,4,5,6,7,8]，合并时只需要读取元素5左右相邻的两个元素就可以得到两个子序列的长度

并且之后尝试合并时，只用尝试合并没有被访问过的元素，被访问过的元素已经尽可能的被合并了，对于只访问没被访问过的元素以及更新时为什么只更新区间端点，有另外一种说法：

(1). 为什么只更新端点? 答：因为中间点会被 if num not in hash_dict: 过滤掉，不会进入下面的逻辑。进入下面的处理逻辑的必然是GAP，如map中已有2,3，5；现在遍历至4才会进入下面的处理逻辑， 此时，left = 2，right = 1，加入4后形成新的连续序列，最大连续长度为4；最后更新的时候，也只需要更新map[2] = 4以及map[5] = 4即可。因为之后，3，4均不会被再次访问，只有当出现1或者6的时候，才会访问map[2]和map[5], 中间的map[2]、map[3]、map[4]永远不会再被访问到。

(2). 为什么 hash_dict[num] = 1 可以随意赋值? 答：诚如评论区的各位同行所言，此处赋值的意义仅在于占位；当map为空加入第一个元素时，left = right = 0，此时，无论给hash_dict[num]赋多少，最后都会被后面的值(hash_dict[num - left] = hash_dict[num - right] = hash_dict[num - 0])覆盖；而当left或right 不等于0时， 由于上述(1)的原因，中间值永远不会被访问到，因此，赋啥值就随意了，此时赋值只起占位作用，防止 if num not in hash_dict: 再次进入处理逻辑。

总结起来就是合并时只用到了子序列的区间端点，合并之后，当前元素变成了区间内的元素，所以核心就是更新区间端点

执行流程

1. 遍历所有元素

2. 如果当前元素没有被访问过，那么就尝试合并

   注意c++中unordered_map访问一个不存在的元素时，之后会自动将这个元素存储，所以判断一个元素是否被访问过不能根据是否存在于容器中来判断，而是判断其值是否为0

3. 获取当前元素左右可能存在的子序列的长度，尝试合并

4. 合并之后更新新的子序列的区间端点值

5. 有了新的连续子序列长度，查看是否需要更新最长的连续子序列长度

6. 重复上述步骤

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    //只能用常数时间，所以不能使用排序
    //数字太大，也不建议使用稀疏的字典
    //从元素没出现在map中开始理解
    int longestConsecutive(vector<int>& nums) {
        if(nums.size()==0)
            return 0;
        unordered_map<int,int> umap;
        int res=1;
        for(auto num:nums){
            //当前元素不在map中
            if(umap[num]==0){
                //尝试将左右两边的游离区间合并
                //因为umap访问了不存在的元素之后会自动创建
                //所以访问没访问过的元素需要使用是否等于0来判断
                int left=umap[num-1];
                int right=umap[num+1];
                int length=left+right+1;
                //尝试找到最长的连续序列
                res=max(res,length);

                //当前元素更新长度只是为了占位
                umap[num]=1;
                //区间端点更新才是核心
                umap[num-left]=length;
                umap[num+right]=length;
            }
        }
        return res;
    }
};

总结

主要就是理解更新时更新的是新区间端点的值，而不是其他的值，因为下一次合并时只会用到这个区间端点