longest-consecutive-sequence 题解

class Solution {
public:
    /**
     * 
     * @param num int整型vector 
     * @return int整型
     */
    int longestConsecutive(vector<int>& num) {
        // write code here
        if(num.size()<=1) return num.size();//长度<=1直接返回当前长度
        int max=num[0];
        int min=num[0];
        int i;
        int r=1;
        int temp=0;
        for(i=1;i<num.size();i++){//遍历找出最大最小值
            if(num[i]<min) min=num[i];
            else if(num[i]>max) max=num[i];
        }
        bool d[max-min+1];//d数组长度为max-min+1，即按照num的取值范围给d分配空间
        //d[0]代表min在num中是否存在，d[1]代表min+1在num中是否存在……d[i]代表min+i在num中是否存在
        //d[0]代表num中最小值min的存在性，必然为1；
        //d[max-min+1]代表num中最大值max的存在性，也必然为1；
        memset(d,0,max-min+1);//初始化d为0
        for(i=0;i<num.size();i++){//遍历num给数组d赋值
            d[num[i]-min]=1;
        }
        for(i=0;i<max-min+1;i++){//检测数组d中最多有多少个连续的true即可
            if(d[i]==1) temp++;
            else{
                r=temp>r?temp:r;
                temp=0;
            }
        }
        r=temp>r?temp:r;
        return r;
    }
};