128. Longest Consecutive Sequence

解題思路

基本上就是把不同的連續數列串在一起，每串的頭是最小的數，ex: 1->2->3->4。

所以先用 set 紀錄整個 array 中有哪些數字，接著再從頭看起。若該數是串的頭(不存在 nums[i]-1)，哪麼就計算該串的長度(用 set 一直檢查 nums[i]+offset 存不存在)。

程式碼

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.size() <= 1) return nums.size();
        
        set<int> s;
        for(int i=0; i<nums.size(); i++)
            s.insert(nums[i]);
        
        int maxLen = 1;
        for(int i=0; i<nums.size(); i++)
        {
            // check if it the head of seq first
            if(!s.count(nums[i] - 1))
            {
                int curLen = 1, offset = 1;
                while(s.count(nums[i] + offset))
                {
                    offset++;
                    curLen++;
                    maxLen = max(maxLen, curLen);
                }
            }
        }
        return maxLen;
    }
};