可以只用一个哈希表记录每个数字所能构成的最大长度

当扫描到一个新数字时，找该数字左右数字的最大长度，合并后，更新该数字和新连续序列左右数字的哈希值。

如果当前扫描到的数已经在哈希表中了，则直接跳过。

有道理！哈希表中记录每个数为边界的最大长度，则只有区间边界的数有意义，如果遇到内部的数，我们直接跳过。当遍历到 $x$ 时，先求出 $x-1$ 的最大长度，则由于 $x$ 第一次遍历到，所以 $x-1$ 如果存在，则一定是某个区间的右端点，同理 $x+1$ 一定是某个区间的左端点。所以我们同时开两个哈希表，记录左右两边的哈希值是多余的，仅需一个哈希表即可。

赞

“tr_left[x - left] = max(tr_left[x - left], left + 1 + right);”为什么要取max呢，left+1+right不就应该是当前以x-left为左端点的序列长度最大值吗

所有极大区间两端的点存储的tr_left和tr_right都是整个区间的长度，但区间内的点存储的长度可能比实际值要小。
可以试试这个样例，正确答案是5，如果去掉max操作会得到4：

[-6,8,-5,7,-9,-1,-7,-6,-9,-7,5,7,-1,-8,-8,-2,0]

应该说取最大值是为了处理重复数字吧？

即使数字没有重复，也是有这个问题的。实际上是因为我们没有删除冗余的小区间，如果合并区间的同时把冗余小区间删除，就没有这个问题了。

如果仍有问题，可以在代码中把每一步所维护的所有区间打印出来看一下。

yxc 太神啦~~

// 现在感觉这个方法最简单
// O(n)，每个点要么作为起点，要么作为扩展点

    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> us(nums.begin(), nums.end());
        int res=0;
        for(const auto& n: nums)
        {
            // 只去看自己作为起点的情况，只有n-1不存在，自己才能是起点
            if(us.find(n-1)!=us.end()) continue;

            // 看看能延伸多长
            int start=n;
            int len=1;
            while(us.find(start+1)!=us.end())
            {
                len++;
                start++;
            }
            res=max(res, len);
        }
        return res;
    }    

y神，这道题用并查集怎么做呢

那种做法本质上是单链表，只是代码有点像并查集。一开始将所有点x的父节点初始化成x + 1，然后按任意顺序遍历所有点，对于每个点，如果其父节点存在，则走到父节点，直到不能走为止，那么最后走到的点就是整段的最大值，然后回溯的时候将所有点的父节点改成刚刚找到的根节点即可。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {

        int res = 0;
        unordered_map<int,int>F;
        for(auto x:nums)
        {
          if(F[x])continue;//三个点同时判重
          F[x]=1;//标记
          int left=F[x-1];//记录左右点包含的点个数
          int right=F[x+1];
          F[x-left]=right+left+1;//更新左右边界区间内点的个数
          F[x+right]=right+left+1;
          res=max(res,right+left+1);
        }
      return res;
    }


};//根据下面讨论区大佬的观点写的

很棒！

感觉很难想出来这种做法，是怎样联想到的，或者哪个例题衍生的

多做题就好了，量变引起质变

讨论里的

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int maxs = 0;
        unordered_map<int,int> range;
        for (int x: nums) {
            int l = x;
            int r = x;
            if (range[x] > 0) continue;
            l = l - range[x - 1];
            r = r + range[x + 1];

            range[l] = r - l + 1;
            range[r] = r - l + 1;
            range[x] = max(range[x], 1); //  注意这里
            maxs = max(maxs, r - l + 1);

        }
        return maxs;
    } 
};

棒！

哈哈 怎么感觉一个哈希有点dp的味道！

对滴，有点像