128. 最长连续序列 #

class Solution {
    public int longestConsecutive(int[] nums) {
        int len=nums.length;
        HashSet<Integer> set=new HashSet<>();
        for(int i:nums){
            set.add(i);
        }
        int maxLen=0;
        int laseMin=Integer.MAX_VALUE;
        int laseMax=Integer.MAX_VALUE;
        for(int i=0;i<len;i++){
            if(laseMax!=Integer.MAX_VALUE&&laseMin!=Integer.MAX_VALUE){
                if(nums[i]<=laseMax&&nums[i]>=laseMin)
                    continue;
            }
            int cur=nums[i];
            int min=cur;
            int max=cur;
            int count=1;
            while(set.contains(++cur)){
                count++;
                max=cur;
            }
            cur=nums[i];
            while(set.contains(--cur)){
                count++;
                min=cur;
            }
            maxLen=Math.max(maxLen,count);
            laseMin=min;
            laseMax=max;
        }
        return maxLen;
    }
}

class Solution {
    public int longestConsecutive(int[] nums) {
        // 特判：空数组就直接返回 0
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // 1. 放入 HashSet 去重 + 便于 O(1) 查询
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        // 2. set2 用来记录每个数字所属的 [min, max] 区间
        //    这样下次遇到这个数字，就不必重复向左、向右搜索
        Set<Integer> set2 = new HashSet<>();

        int maxLen = 0;

        // 3. 遍历原数组 这里其实使用set进行遍历也可以，效果差不多，因为下面接着就是做set2.contains(num)的处理，所以效果差别不多
        for (int num : nums) {
            // 若 set2 里已经包含此数字，说明它之前被处理过，跳过
            if (set2.contains(num)) {
                continue;
            }

            //  找到 num 所在连续区间的左右边界
            int left = num;
            int right = num;

            // 向左扩张
            while (set.contains(left - 1)) {
                left--;
            }
            // 向右扩张
            while (set.contains(right + 1)) {
                right++;
            }

            int curLen = right - left + 1;
            maxLen = Math.max(maxLen, curLen);

            //将此区间内所有数字都记录到 set2
            for (int x = left; x <= right; x++) {
                set2.add(x);
            }
        }

        return maxLen;
    }
}

class Solution {
    public int longestConsecutive(int[] nums) {
        // 特判：空数组就直接返回 0
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // 1. 放入 HashSet 去重 + 便于 O(1) 查询
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int maxLen = 0;

        // 3. 遍历去重之后的数组，否则会超时
        for (int num : set) {
            if (set.contains(num-1)) {
                continue;
            }
            int right=num;
            int left=num;
            // 向右扩张
            while (set.contains(right + 1)) {
                right++;
            }
            int curLen = right - left + 1;
            maxLen = Math.max(maxLen, curLen);
        }

        return maxLen;
    }
}