目录

题目描述

整体思路

具体代码

---

题目描述

原题链接

整体思路

        首先看到找连续升序排序的最长序列长度，想到对数组进行排序预处理。但是排序算法时间复杂度需要O(nlogn)，题目要求时间复杂度为O(n)。因此不能进行排序与处理

        接着想到数据结构哈希表，哈希表适合用于无序的数据问题。因此可以将数组元素全部存入哈希表，而后遍历哈希表，每次遍历都要找出连续升序排序的序列的头。找到头就要继续找下一个元素直到序列尾。然后保留每次寻找过程的序列长度的最大值。

具体代码

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.size()==0) return 0;//题目中说了数组长度可能为0
        set<int> s;
        for(int i:nums) s.insert(i);
        int ml=INT_MIN;
        for(int i:s){
            if(!s.count(i-1)){//连续升序序列中，不可能有比序列头小1的元素
                int cl=1;
                int nxt=i+1;
                while(s.count(nxt)){
                    cl++;
                    nxt++;
                }
                ml=max(ml,cl);
            }
        }
        return ml;
    }
};