//排序法，时间O(nlogn)，使用STL，只是验证一下思想，非正解；

class Solution {

public:

    int longestConsecutive(vector<int>& nums) {

        sort(nums.begin(),nums.end());

        int res=;

        for(int i=;i<nums.size();i++){

            int step=,len=;

            while(i+step!=nums.size()-&&nums[i+step+]-nums[i+step]<=){

                if(nums[i+step]+==nums[i+step+]) len++;

                step++;

            }

            res=max(res,len);

            i+=step;

        }

        return res;

    }

};

//哈希表结合染色，建立一个哈希表，然后遍历之后计数每个元素周围所有相邻元素并染色，记录个数；O(n)复杂度

class Solution {

public:

    int longestConsecutive(vector<int>& nums) {

        int len=nums.size();

        if(len<=) return len;

        unordered_map<int,int> m;

        int res=;

        for(int n:nums)

            m[n]=;

        for(int n:nums){

            int i=n,j=n;

            int cnt=;

            if(m[n]==)

                continue;

            else

                m[n]=;

            while(m[i+]==){

                i++;

                m[i]=;

            }

            while(m[j-]==){

                j--;

                m[j]=;

            }

            cnt=i-j+;

            res=cnt>res?cnt:res;

        }

        return res;

    }

};

/****

通过哈希表记录边界信息

neither i+1 nor i-1 has been seen: m[i]=1;

both i+1 and i-1 have been seen: extend m[i+m[i+1]] and m[i-m[i-1]] to each other;

only i+1 has been seen: extend m[i+m[i+1]] and m[i] to each other;

only i-1 has been seen: extend m[i-m[i-1]] and m[i] to each other.

*****/

class Solution {

public:

    int longestConsecutive(vector<int>& nums) {

        int len=nums.size();

        if(len<=) return len;

        unordered_map<int,int> m;

        int res=;

        for(int i:nums){

            if(m[i]) continue;

            //后面表达式为将m[i]和这一段连续序列的边界全部赋值为他的长度

            //边界只可能为m[i-m[i-1]]到m[i+m[i+1]]，m[i]到m[i+m[i+1]],m[i-m[i-1]]到m[i]这几种情况，因此更新三者的值为新连续序列的长度即可

            //又因为没有的元素哈希值为0，所以m[i]左右元素的m[i-1]+m[i+1]+1为新序列的长度；

            res=max(res,m[i]=m[i+m[i+]]=m[i-m[i-]]=m[i-]+m[i+]+);

        }

        return res;

    }

};

/****

通过哈希set

将nums转化为哈希set,然后对哈希set进行遍历，寻找连续片段的左边界，然后num+1进行遍历。

可以证明每个元素将被访问2遍，for中一遍，while一遍，所以time O(n),space O(n);

由于int会产生越界，可以使用long,也可以进行边界检测，INT_MAX break;

*****/

class Solution {

public:

    int longestConsecutive(vector<int>& nums) {

        int res=;

        unordered_set<int> h(nums.begin(),nums.end());

        for(int num:nums){

            int l=;

            if(!h.count(num-)){

                while(h.count(num)!=){

                    ++l;

                    if(num==INT_MAX) break;

                    ++num;

                }

                res=res>l?res:l;

            }

        }

        return res;

    }

};

/****

通过哈希table

solution 1: hashtable (key,len)

case1: no neighboors

h[num]=1;

case2: one neighboor

l=h[num-1] or r=h[num+1]

h[num]=h[num-1]=l+1 or h[num]=h[num+1]=r+1

case3: two neighboors

l=h[num-1]

r=h[num+1]

h[num]=h[num-1]=h[num+1]=l+r+1

*****/

class Solution {

public:

    int longestConsecutive(vector<int>& nums) {

        int res=;

        unordered_map<int,int> h;

        for(int num:nums){

            if(h[num]!=) continue;

            int l=h[num-];

            int r=h[num+];

            int t=l+r+;

            h[num]=h[num+r]=h[num-l]=t;

            res=res>t?res:t;

        }

        return res;

    }

};

/****

通过哈希set

将nums转化为哈希set,然后对哈希set进行遍历，寻找连续片段的左边界，然后num+1进行遍历。

可以证明每个元素将被访问2遍，for中一遍，while一遍，所以time O(n),space O(n);

由于int会产生越界，可以使用long,也可以进行边界检测，INT_MAX break;

*****/

class Solution {

public:

    int longestConsecutive(vector<int>& nums) {

        int res=;

        unordered_set<int> h(nums.begin(),nums.end());

        for(int num: nums){

            int l=;

            if(h.count(num-)==){

                while(h.count(num)>){

                    l++;

                    if(num==INT_MAX) break;

                    num++;

                }

            }

            res=res>l?res:l;

        }

        return res;

    }

};