[力扣 Hot100]Day3 最长连续序列

题目描述

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

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

出处

思路

此题可用带排序的哈希表，先构建哈希表，然后遍历哈希表，维护一个工作数和一个最长记录（初始值均为1），若相邻两个哈希表项的key相差1，则工作数++，否则视情况更新最长记录并把工作数归1。
value不起作用，题目无需考虑存在多个相同key的问题。

代码

class Solution {
   
public:
    map<int, int> hash;
    int longestConsecutive(vector<int>& nums) {
   
        if(nums.empty())
            return 0;
        for(auto i : nums){
   
            hash[i] = i;
        }
        int max=1,tmp=1;
        auto pre=hash.begin();
        auto it=++hash.begin();
        while(it!=hash.end()){
   
            if(it->first==pre->first+1) {
   //若连续
                tmp++;
                if (tmp > max)
                    max = tmp;
            }
            else
                tmp=1;
            pre++;
            it++;
        }
        return max;
    }
};