一. 題目描述
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
二. 題目分析
這道題有兩個技巧：
哈希表插入和查找一個數(shù)的時間復雜度為O(1)；因此，可以使用哈希表來保存數(shù)組，以保障對于數(shù)組中的元素的查找是常量時間； 一個數(shù)與它相鄰的數(shù)都在同一個連續(xù)子序列中，因此，可以在某個數(shù)開始進行最長連續(xù)子序列判斷的時候，可以將與它在同一連續(xù)子序列中的元素標記為不作為判斷的開始，因為該元素所在的連續(xù)子序列處理過了，這樣就可以大大較少比較次數(shù)，降低計算復雜度；由于C++實現(xiàn)中的哈希表是一個無序字典類型，因此，可以將數(shù)組元素的值作為關鍵字，技巧2中每個元素的標記位作為每一個關鍵字的值，
leetcode筆記：Longest Consecutive Sequence
。 對于數(shù)組中的每一個元素，先判斷其所在連續(xù)子序列是否已經(jīng)處理過了，如果已經(jīng)處理過了，則直接處理下一個元素；如果還沒處理過，則以其為中心，向左向右查找是否有相鄰的數(shù)存在數(shù)組中，如果存在，就將長度加1，并將該元素的標記位置位，表示該元素所在的連續(xù)子序列已經(jīng)處理過了，一直查找下去，直到相鄰的數(shù)字不存在數(shù)組中為止，記錄序列的長度，然后處理下一個元素。按照這個方法，在進行最長連續(xù)子序列查找的過程中，每個元素只被訪問一次，因此計算復雜度為O(n)。
在創(chuàng)建哈希表的過程中，計算復雜度也為O(n)，因此，整個算法的時間復雜度為O(n)+O(n)=O(n)。
三. 示例代碼
<code class="hljs cpp">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; }};</int,></int></code>四. 小結
該題可以在進行一次最大連續(xù)子序列查找的過程中將所有在該連續(xù)子序列中的元素進行標記，從而減少尋找最長連續(xù)子序列的這個過程，降低計算復雜度，使得這個尋找過程的計算復雜度為O(n)，