上周刷完了leetcode“热题100”题单中的所有简单题，完成了对算法与数据结构的基础复习，接下来预计按照每天至少1道题的节奏，对leetcode“热题100”题单中的题目进行完成。

128.最长连续序列

题目要求从一个未排序的数组中，找到一个最长的连续序列，自然的想法是，以数组中的每个元素为起始，分别判断以其为起始的最长序列的长度。于是，写出了以下代码：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) 
    {
        unordered_map<int,int> mp;
        for(int i=0;i<nums.size();i++)
        {
            mp[nums[i]]=nums[i];
        }
        int ans=0;
        for(int i=0;i<nums.size();i++)
        {
            int temp_ans=1;
            int temp=nums[i];
            while(mp.count(++temp))
            {
                temp_ans++;
            }
            if(temp_ans>ans) ans=temp_ans;
        }
        return ans;
    }
};

显然，这是一种很暴力的方法（当然，不是最暴力），时间复杂度达到了O（n²），空间复杂度达到O（n），这里运用了哈希表，将查找“下一个元素”的复杂度降低了。然而题目要求的复杂度是O（n），显然，超时了。

于是，通过阅读官方题解，找到了优化的方法，可以判断一个元素的前一个数字是否存在，若存在，证明其一定不是最长序列的开头，于是跳过。用这种方式，可以将复杂度降低到O（n），代码如下：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) 
    {
        unordered_map<int,int> mp;
        for(int i=0;i<nums.size();i++)
        {
            mp[nums[i]]=nums[i];
        }
        int ans=0;
        for(int i=0;i<nums.size();i++)
        {
            int temp_ans=1;
            int temp=nums[i];
            if(mp.count(temp-1)) continue;//跳过非序列头的元素
            while(mp.count(++temp))
            {
                temp_ans++;
            }
            if(temp_ans>ans) ans=temp_ans;
        }
        return ans;
    }
};

当然，还有优化空间，此处，更合适的是使用unordered_set。