LeetCode 128 Longest Consecutive Sequence

思路

首先可以想到一个O(nlogn)时间的算法：排序。
对于O(n)的时间，使用set保存数组中的数，对于每一个元素都进行左右找下一个元素是否在数组中，然后标记是否被访问过(这里将该数从set中删除作为该标记)，直到左右的下一个元素都不在数组中，这时可以记录下right-left-1作为一个候选长度【right-left-1是因为right和left最终都会停在下一个不存在的元素上】。然后重复上述过程，直到所有的元素都被访问过。

复杂度

时间复杂度O(n)，因为所有元素仅会被访问过1次。
空间复杂度O(n)

代码

class Solution {
    public int longestConsecutive(int[] nums) {
    if(nums == null || nums.length == 0)return 0;Set<Integer> set = new HashSet<>();int ans = 0;for(int i : nums) {
    set.add(i);}for(int i : nums) {
    if(set.contains(i)) {
    set.remove(i);int left = i - 1, right = i + 1;while(set.contains(left)) {
    set.remove(left);left--;}while(set.contains(right)) {
    set.remove(right);right++;}ans = Math.max(ans, right - left - 1);}}return ans;}
}