題目描述：給一個(gè)未排序的整數(shù)數(shù)組痘儡，查找其中最長連續(xù)元素序列的長度狮崩。如[100, 4, 200, 1, 3, 2]找到[1, 2, 3, 4]，返回4丘薛。要求復(fù)雜度為O(n)嘉竟。
分析：由于限定了線性復(fù)雜度所以不能用排序了。第一個(gè)想法是設(shè)一個(gè)長度為給定的數(shù)組中最大數(shù)mx的標(biāo)記數(shù)組洋侨，記錄給定數(shù)組中從0～mx 的元素是否出現(xiàn)舍扰，然后遍歷一遍標(biāo)記數(shù)組，找連續(xù)1的最長長度希坚。提交發(fā)現(xiàn)數(shù)據(jù)存在負(fù)數(shù)妥粟，思考不全面。還是用map來記錄吏够。
代碼：雖然是兩重循環(huán)勾给，但實(shí)際上最多只會遍歷數(shù)組一次。因?yàn)閷σ粋€(gè)數(shù)左右的查找是連續(xù)的锅知，而子序列是有斷點(diǎn)的播急。故復(fù)雜度為O(n)。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
//無序容器售睹，快速查找刪除桩警，不擔(dān)心略高的內(nèi)存時(shí)用unordered_map；有序容器穩(wěn)定查找刪除效率昌妹，內(nèi)存很在意時(shí)候用map捶枢。
unordered_map<int, bool> used;
//遍歷nums握截，i是其中元素，類似Python 中for i in nums 的用法
for (auto i : nums)
used[i] = false;
int longest = 0;
for (auto i : nums)
{
if (used[i]) continue; //已經(jīng)遍歷過
int len = 1;
for (int j = i + 1; used.find(j) != used.end(); j++) //查找比 i 大的部分
{
used[j] = true;
len ++;
}
for (int j = i - 1; used.find(j) != used.end(); j--)
{
used[j] = true;
len ++;
}
longest = max(longest, len);
}
return longest;
}
};
