题目描述

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

样例

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

根据题意可知，存在vector为空或只有一个元素的情况，因此特判

算法1：排序+循环

1、排序

2、设置一个答案nAns，一个临时变量res(初始值为1：每个元素都可以自身成为一个序列，因此初始化为1)

3、遍历：如果nums[i]==nums[i-1]+1则将res加加，否则，就代表会出现新的可能成为答案的序列，此时将nAns更新，并将res重新赋值为1

上述考虑存在部分问题：样例中存在重复元素，因此不可以将nums[i]直接和nums[i-1]进行比较，可以设置一个nLast变量，表示上一个非重复变量是多少，也需要实时更新nLast变量

时间复杂度

O(nlogn)，排序时间复杂度为O(nlogn)，遍历为O(n)

C++ 代码

class Solution {
public:
/*
根据题意可知，存在vector为空或只有一个元素的情况，因此特判(只有一个元素的情况被写入了for判断中，因此只特判为空的情况)

第一种做法：
    1、排序
    2、设置一个答案nAns，一个临时变量res(初始值为1：每个元素都可以自身成为一个序列，因此初始化为1)
    3、遍历：
        如果nums[i]==nums[i-1]+1则将res加加
        否则，就代表会出现新的可能成为答案的序列，此时将nAns更新，并将res重新赋值为1

上述考虑存在部分问题：
    样例中存在重复元素，因此不可以将nums[i]直接和nums[i-1]进行比较，
    可以设置一个nLast变量，表示上一个非重复变量是多少，也需要实时更新nLast变量
*/
    int longestConsecutive(vector<int>& nums) {
        // 特判没有元素的情况
        if(nums.size()==0) return 0;

        // 排序
        sort(nums.begin(),nums.end());

        int nAns=0;
        int nRes=1;
        int nLast=nums[0];
        for(int i=1;i<nums.size();i++)
        {
            // 找出和当前nLast不同的下一个数
            while(i<nums.size()&&nums[i]==nLast) ++i;

            if(i==nums.size()) break; // 如果此时i已越界，则说明当前遍历的序列数值都相同，直接退出循环

            if(nums[i]==nLast+1) 
            {
                ++nRes;
            }
            else  // 和前一个连续序列断开，因此更新答案，并将nRes赋值为1，开始计数新的序列
            {
                nAns=max(nAns,nRes);
                nRes=1; // 当前数字！=前一个数字(nLast)，因此当前数字可能成为新的答案序列，因此nRes设置为1
            }

            // 此时的nums[i]肯定不等于nLast，如果等于会在上面的while循环中被遍历掉
            nLast=nums[i]; 
        }

        // 1、如果最后一个元素也在答案序列中，则最后会走向if，不会走向else中的更新nAns，但需要更新nAns
        // 2、要么就在if中不断更新nAns,但会漏掉只有一个元素的情况，则需要特判一个元素的情况
        nAns=max(nAns,nRes);

        /*
        此处会将最后一个元素加入答案中，因此最后需要单独处理该元素，类似于贪心的某题，因此一定要在代码中体现
        */

        return nAns;
    }
};

算法2

哈希表+巧妙实现O(n)判断

时间复杂度

O(n)：每个序列的第一个元素都会向后不断遍历，加起来只会遍历整个nums，因此为O(n)

C++ 代码

class Solution {
public:
/*
该题的场景为：多个连续数字的序列，比如  
 1 2 3 4 5    8 9   80 81 82 83 84 85 86 87
 _________    ___   ______________________

 我们不能选择每个序列的中间某个元素向后遍历或向前遍历，这两种方式都无法在O(n)内找到连续数字的最大序列。
 比如，找到3，向后遍历，遍历到5时，则找出了连续序列 3 4 5，长度为3 ，但3的前面是2，2应该也在该连续序列中，因此，不能选择中间元素向后遍历
 选择中间元素3遍历后，还会发生2向后遍历，则会造成O(n^2)的时间复杂度，题目前提是无序的，因此2也会向后遍历
 因此只考虑每个序列的第一个元素，其他元素皆不考虑，实现O(n)

需要找到某个元素，该元素的前一个值是不存在于nums中的(即每个序列的第一个元素)，从该元素向后加加遍历，直到遍历到的数不存在于nums中，则该序列为可能的答案，将多个可能的答案进行max

每一个序列在处理时，都只会考虑到第一个元素
前面已将元素都放入了unordered_set，则哈希表中元素都是唯一的，没有重复的元素出现
即使每个序列的第一个元素在nums中出现了多次，在for循环遍历哈希表时，也只会遍历到一次，此处避免了多个元素遍历一次(避免了O(n^2))

1、利用哈希表存储nums，实现去重，避免了相同元素向后进行多次遍历
2、遍历哈希表，如果当前元素-1不存在于哈希表中，则表示当前元素为序列的起始元素，则将该值不断加加，同时判断是否存在于哈希表中
    比如 当前元素为x，nums中不存在x-1，存在 x-y的所有元素，则该序列为   x  x+1  x+2  x+3  x+4  x+5 ... y
    该序列长度为 y-x+1
3、每找到一个新的序列，都需要更新一次答案
*/
    int longestConsecutive(vector<int>& nums) {
        if(nums.size()==0) return 0;

        unordered_set<int> hash;
        for(int i=0;i<nums.size();i++)
        {
            hash.insert(nums[i]);
        }

        int nLast=0;
        int nAns=0;
        for(int nCur:hash)
        {
            if(hash.find(nCur-1)==hash.end()) // 当前元素-1不存在于nums中，即在哈希表中找不到 当前元素-1
            {
                nLast=nCur+1; // 连续数字
                while(hash.find(nLast)!=hash.end()) // 哈希表中能找到连续数字，则不断向后加加并判断
                {
                    ++nLast;
                }
                nAns=max(nAns,nLast-nCur);
            }
        }
    return nAns;
    }
};