1.题目

https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/ti-mu-fen-xi-ji-yi-hua-sou-suo-bing-cha-ji-ji-lu-d/

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;//元素个数
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

3.法二：dfs-记忆化搜索

不能用set或map等基于树的容器（容器的插入与查找时间复杂度为额为logn），只能执行常数次的插入或查找。

有向无环图求最长路：对于每个v都指向v+1。mp[v]表示以v为起点的最长路的长度，所以可以得出递归式：$mp[index]=mp[index+1]+1$，而递归边界：哈希表中以index为key值的value为0时，则$mp[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;
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/113806913