大学 网站开发 专业百度推广app怎么收费

题目描述

给定一个未排序的整数数组 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;}elsetmp=1;pre++;it++;}return max;}
};