128. Longest Consecutive Sequence
給定一個未排序的整數數組 nums，返回最長的連續元素序列的長度。
你必須編寫一個時間複雜度為 O(n) 的算法。
範例：
輸入：nums = [100, 4, 200, 1, 3, 2] 輸出：4 解釋：最長的連續元素序列是 [1, 2, 3, 4]。因此它的長度是 4。
Python
from typing import List
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if not nums:
return 0
num_set = set(nums)
longest_streak = 0
for num in num_set:
# Only check for the start of a sequence
if num - 1 not in num_set:
current_num = num
current_streak = 1
while current_num + 1 in num_set:
current_num += 1
current_streak += 1
longest_streak = max(longest_streak, current_streak)
return longest_streak
31.84MB, 340ms
C++
#include <vector>
#include <unordered_set>
using namespace std;
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if (nums.empty()) return 0;
unordered_set<int> numSet(nums.begin(), nums.end());
int longestStreak = 0;
for (int num : numSet) {
// Only check for the start of a sequence
if (numSet.find(num - 1) == numSet.end()) {
int currentNum = num;
int currentStreak = 1;
while (numSet.find(currentNum + 1) != numSet.end()) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = max(longestStreak, currentStreak);
}
}
return longestStreak;
}
};
74.5MB, 128ms
Javascript
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function(nums) {
if (nums.length === 0) return 0;
const numSet = new Set(nums);
let longestStreak = 0;
for (const num of numSet) {
// Only check for the start of a sequence
if (!numSet.has(num - 1)) {
let currentNum = num;
let currentStreak = 1;
while (numSet.has(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
};
72.83MB, 113ms
