Discuss

二.解题技巧

1.哈希表插入和查找一个数的时间复杂度为O(1)；因此，可以使用哈希表来保存数组，以保障对于数组中的元素的查找是常量时间；

2.一个数与它相邻的数都在同一个连续子序列中，因此，可以在某个数开始进行最长连续子序列判断的时候，可以将与它在同一连续子序列中的元素标记为不作为判断的开始，因为该元素所在的连续子序列处理过了，这样就可以大大较少比较次数，降低计算复杂度；

三.实现代码

class Solution
{
public:
    int longestConsecutive(vector<int> &num)
    {
        // get the size of the num
        int Size = num.size();
        // build the hash_table
        unordered_map<int, bool> HashTable;
        for (int Index = 0; Index < Size; Index++)
        {
            int Tmp = num[Index];
            HashTable[Tmp] = false;
        }
        // find the longest consecutive sequence
        int LongestNumber = 1;
        for (int Index = 0; Index < Size; Index++)
        {
            int Tmp = num[Index];
            if (HashTable[Tmp])
            {
                continue;
            }
            int TmpSequence = 1;
            while (HashTable.find(++Tmp) != HashTable.end())
            {
                HashTable[Tmp] = true;
                TmpSequence++;
            }
            Tmp = num[Index];
            while (HashTable.find(--Tmp) != HashTable.end())
            {
                HashTable[Tmp] = true;
                TmpSequence++;
            }
            if (LongestNumber < TmpSequence)
            {
                LongestNumber = TmpSequence;
            }
        }
        return LongestNumber ;
    }
};

四.体会