题目描述

给定一个无序的整数类型数组，求最长的连续元素序列的长度。例如：给出的数组为[1000, 4, 2000, 1, 3, 2],
最长的连续元素序列为[1, 2, 3, 4]. 返回这个序列的长度：4 你需要给出时间复杂度在O（n）之内的算法

思路

第一反应使用哈希表，然后是想到map，但题目要求时间复杂度O(n)，map是有序的所以要用无序的，又输入是vector,所以使用同样是基于hash表的unorder_set

接着只要遍历查找每个数的+1，-1的值是否存在，记录序列长度

每次将序列长度更新为最长的

哈希函数的使用方法

class Solution {   public:    /**     *      * @param num int整型vector      * @return int整型     */    int longestConsecutive(vector
   
    & num) {           // write code here        // 使用哈希表         unordered_set
    
      uset(num.begin(), num.end());        int res = 0;                for(auto item:num){               int left = item - 1;            int right = item + 1;            int cnt = 1;            // 遍历找left，left每次减一            while(uset.count(left) != 0){                   uset.erase(left--);                cnt++;            }                        while(uset.count(right) != 0){                   uset.erase(right++);                cnt++;            }            // 每次更新最长的序列            res = max(res, cnt);        }        return res;    }};

在这里插入图片描述