128. Longest Consecutive Sequence
HashSet. Time = O(n), Space = O(n)
注意 map.put(cur - left, val);
和 map.put(cur + right, val);
不需要更新所有元素,只更新 boundary 即可。
class Solution {
public int longestConsecutive(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int longest = 0;
for (int i = 0; i < nums.length; i++) {
int cur = nums[i];
if (map.containsKey(cur)) {
continue;
}
int left = map.containsKey(cur - 1) ? map.get(cur - 1) : 0;
int right = map.containsKey(cur + 1) ? map.get(cur + 1) : 0;
int val = left + 1 + right;
if (val > longest) {
longest = val;
}
map.put(cur, val);
map.put(cur - left, val);
map.put(cur + right, val);
}
return longest;
}
}