class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
int ans = 0;
for (int num : nums) {
set.add(num);
}
for(int i = 0;i < nums.length; i ++) {
int x = nums[i];
// 说明x是连续序列的开头元素
if (!set.contains(x - 1)) {
while(set.contains(x + 1)) {
x ++;
}
}
ans = Math.max(ans, x - nums[i] + 1);
}
return ans;
}
}
Python Code:
class Solution:
def longestConsecutive(self, A: List[int]) -> int:
seen = set(A)
ans = 0
for a in A:
t = a
# 说明 t 是连续序列的开头元素。加这个条件相当于剪枝的作用,否则时间复杂度会退化到 N ^ 2
if t + 1 not in seen:
while t - 1 in seen:
t -= 1
ans = max(ans, a - t + 1)
return ans
JS Code:
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
set = new Set(nums);
let max = 0;
let temp = 0;
set.forEach((x) => {
// 说明x是连续序列的开头元素。加这个条件相当于剪枝的作用,否则时间复杂度会退化到 N ^ 2
if (!set.has(x - 1)) {
temp = x + 1;
while (set.has(y)) {
temp = temp + 1;
}
max = Math.max(max, y - x); // y - x 就是从x开始到最后有多少连续的数字
}
});
return max;
};