題目鏈接
tag:
- Hard；
question
??Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
思路：
??本題要求O(n)解決問(wèn)題属划，我們可以借助哈希表吟孙，建立值與index的映射相速，隨后遍歷數(shù)組浑测，針對(duì)每一個(gè)元素在哈希表中查找比它大的連續(xù)數(shù)的個(gè)數(shù)即可芥颈，代碼如下：
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if (nums.empty()) return 0;
if (nums.size() == 1) return 1;
unordered_map<int, int> m;
for (int i=0; i<nums.size(); ++i) {
m[nums[i]] = i;
}
int res = 0;
for (int i=0; i<nums.size(); ++i) {
int tmp_len = 1;
int tmp_value = nums[i];
while (true) {
if (m.find(++tmp_value) != m.end())
++tmp_len;
else
break;
}
res = max(res, tmp_len);
}
return res;
}
};
