1.题目
2.法一：用sort
初级解法：用sort排序和用unique去重后for循环遍历一遍数组，如果当前和上一个数字之差为1，则count累加1；如果当前数字和上一个数字之差不为1，则重新设count为1计算。
为啥要去重呢：题目说的数字连续的最长序列，如第二个组测试用例，0012345678，就不包括重复的0了，而是从0到8计数。
复杂度：没达到O(n)的时间复杂度——因为用了sort排序，时间复杂度是O(nlog n)。
class Solution { public: int longestConsecutive(vector<int>& nums) { if(nums.size()==0) return 0; sort(nums.begin(),nums.end());//从小到大排序 auto quchong=unique(nums.begin(),nums.end());//去重 //一次for遍历即可 int a=0,max=1,count=1; for(int i=1;i<nums.size();i++){ if(nums[i]-nums[a++]==1){ count++;//符合连续序列的元素个数 //a++; }else{ count=1;//重新计为1个 //a++; } if(count>max){ max=count; } } return max;//元素个数 } };
3.法二：dfs-记忆化搜索
不能用set或map等基于树的容器（容器的插入与查找时间复杂度为额为logn），只能执行常数次的插入或查找。
有向无环图求最长路：对于每个v都指向v+1。mp[v]表示以v为起点的最长路的长度，所以可以得出递归式：m p [ i n d e x ] = m p [ i n d e x + 1 ] + 1 mp[index]=mp[index+1]+1mp[index]=mp[index+1]+1，而递归边界：哈希表中以index为key值的value为0时，则m p [ i n d e x ] = 0 mp[index]=0mp[index]=0。
注意unordered_map底层是hash表,map底层是红黑树。
class Solution { private: unordered_map<int,int>mp; public: int dfs(int index){//求以index为起点的最长路长度 if(mp.find(index)==mp.end()){//若不在 return 0; } if(mp[index]!=0){ return mp[index]; } return mp[index]=dfs(index+1)+1; } int longestConsecutive(vector<int>& nums) { if(nums.size()==0) return 0; for(auto i:nums){ mp[i]=0;//加入key值，并初始化value } int ans=0; for(auto i:nums){ if(ans < dfs(i)){ ans=dfs(i); } } return ans; } };
