1. 128

longest-consecutive-sequence

2. 算法

• O(n)

http://www.tuicool.com/articles/B7FBb2 http://www.cnblogs.com/kaituorensheng/p/3675632.html

http://www.cnblogs.com/grandyang/p/4276225.html

2.1 set算法

class Solution{
public:
    int longestConsecutive(vector<int>& nums){
        int res=0;
        if(nums.empty())  return -1;
        unordered_set<int> s(nums.begin(),nums.end());
        for(int val:nums){
            if(!s.count(val)) continue;
            s.erase(val);
            int pre=val-1,next=val+1;
            while(s.count(pre)) s.erase(pre--);
            while(s.count(next))  s.erase(next++);
            res=max(res,next-pre-1);
        }

        return res;

    }
};

2.2 哈希

http://www.cnblogs.com/grandyang/p/4276225.html

class  Solution{
public:
    int longConsecutive(vector<int>& nums){
        int res=0;
        unordered_map<int,int> m;
        for(int d:nums){
            if(m.count(d)){
                int left=m.count(d-1)?m[d-1]:0;
                int right=m.count(d+1)?m[d+1]:0;
                int sum=left+right+1;
                m[d]=sum;
                res=max(res,sum);
                m[d-left]=sum;
                m[d+right]=sum;
            }
        }

        return res;
    }
};