【LeetCode】Longest Consecutive Sequence解題筆記

題意：給出一個無序的整型數組，求出最長的連續整數序列，例如[100, 4, 200, 1, 3, 2],的最長連續序列為[1,2,3,4]，傳回序列長度4即可

分析：這個題目如果數組是有序的，則一次周遊就可以得到最長的連續整數長度，但是，題目給出的是無序的序列，是以，第一個思路就有了

思路1：先對數組進行排序（增序或者減序均可），然後周遊數組，如果相鄰兩個元素的內插補點為1（增序）或者-1（減序），則在求出的序列長度上+1即可。

這個時候，忽然看到，題目要求，時間複雜度為O（N），思路1就不符合要求了，因為排序的複雜度，最少也是O(NlgN)，是不滿足要求的，是以，不能花時間對序列進行排序。

排除掉思路1，就開始思考不排序的情況下，如何判斷數組中的數字的連續性。所謂連續，也就是這個數字+1或者-1，例如跟1連續的隻有0與2，那要判斷連續，就隻需要考慮0與2是否在目前的數組裡即可。于是就有了思路2.

思路2：周遊數組，每一個值val，判斷val+1與val-1是否在數組裡，但是，查找的時間複雜度，也至少是O(N)，這樣也是不行的，那就思考，如何把查找的複雜度降低到常量級别，想了很久都沒結果，最後，參考了hash的思想，用空間來換取時間，将數組中的數散列到hash表中，即可以常量O(1)的時間複雜度來判斷數值的存在與否。

思路2可以滿足N的時間複雜度，但是，hash要自己寫，其實也挺麻煩的，研究了stl，才發現有現成的資料結構unordered_set與unordered_map，這兩個資料結構均是以hash方式來做存儲與檢索，我們這個題目中不需要儲存映射關系，是以選用unordered_set作為hash的載體。

同時還有一個細節，就是檢索的時候，是兩個方向的，遞增與遞減，剛開始，我隻向一個方向檢索，hash表一直不變，導緻許多重複的搜尋，送出代碼時，有逾時的錯誤，後面改進為向兩個方向同時檢索，并且，檢索到一個數值之後，将該數值從hash表中清除，最終才AC通過。

代碼：

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		unordered_set<int> hashlist = unordered_set<int>();
		for (int i = 0; i < num.size(); ++ i)
		{
			hashlist.insert(num[i]);
		}

		int maxCon = 0;
		for (int i = 0; i < num.size(); ++i)
		{
			int sub = num[i]-1;
			int tmpLen = 1;
			while (hashlist.find(sub) != hashlist.end())
			{
				tmpLen ++;
				hashlist.erase(sub);
				sub--;
			}
			int add = num[i]+1;
			while(hashlist.find(add) != hashlist.end())
			{
				tmpLen ++;
				hashlist.erase(add);
				add ++;
			}
			if (tmpLen > maxCon)
			{
				maxCon = tmpLen;
			}
		}		
		return maxCon;   
    }
};