給定一個(gè)未排序的整數(shù)數(shù)組盔腔，找出最長(zhǎng)連續(xù)序列的長(zhǎng)度。
要求算法的時(shí)間復(fù)雜度為 O(n)。
示例:
輸入: [100, 4, 200, 1, 3, 2]
輸出: 4
解釋: 最長(zhǎng)連續(xù)序列是 [1, 2, 3, 4]弛随。它的長(zhǎng)度為 4瓢喉。
代碼
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int res = 0;
unordered_set<int> s(nums.begin(), nums.end());
for (int val : nums) {
if (!s.count(val)) continue;
s.erase(val);
int pre = val - 1, next = val + 1;
while (s.count(pre)) s.erase(pre--);
while (s.count(next)) s.erase(next++);
res = max(res, next - pre - 1);
}
return res;
}
};
