128. Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Constraints:
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
class Solution {
public int longestConsecutive(int[] nums) {
int res = 0;
// 使用map存储当前元素n的最大序列长度sum
Map<Integer, Integer> map = new HashMap<>();
for (int n : nums) {
// 重复元素直接跳过
if(map.containsKey(n)){
continue;
}
// 相邻左侧节点计算左侧的最大长度(没有相邻左侧节点直接设置为0)
int left = map.getOrDefault(n-1, 0);
// 相邻右侧节点计算右侧最大长度
int right = map.getOrDefault(n+1, 0);
// 计算当前左右节点累加之后的长度sum，并保存到n中
int sum = left + right + 1;
map.put(n, sum);
// 求res当前最大值
res = Math.max(res, sum);
// 扩大n两侧的数字范围
// n左侧left个节点，更新为sum
map.put(n-left, sum);
// n右侧right个节点，更新为sum
map.put(n+right, sum);
}
return res;
}
}