leetcode128最长连续序列

原题链接:

• https://leetcode.cn/problems/longest-consecutive-sequence/

解法1 哈希集合 标记数

class Solution {
    /**
     * 法1:
     * 哈希集合标记
     */
    public int longestConsecutive(int[] nums) {
        HashSet<Integer>hash = new HashSet<>();
        
        for(var  x : nums){
            hash.add(x);
        }
        
        int ans = 0;
        for(var x : nums){
           // 前一个元素没有在集合中 说明该连续序列没有统计过
            if(hash.contains(x - 1) == false){
                int cur = x;
                while (hash.contains(cur)){
                    cur++;
                }
                ans = Math.max(ans,cur - x);
            }
        }
        return ans;
    }
}

解法2 哈希集合标记 右边界

class Solution {
    /**
     * 法2 : 哈希存储右边界
     */
    public int longestConsecutive(int[] nums) {
        HashMap<Integer,Integer> hash = new HashMap<>();
        
        // 初始化有边界 指向自己
        for(var x : nums){
            hash.put(x,x);
        }
        
        int ans = 0;
        
        for(var x : nums){
            // 如果当前区间没有被遍历过
            if(hash.containsKey(x - 1) == false){
                // 直接取出右边界 x在之前初始化过是不可能为0的
                int right = hash.getOrDefault(x,0);
                while (hash.containsKey(right)){
                    right++;
                }
                // 更新当数的有边界
                hash.put(x,right);
                ans = Math.max(ans,right - x);
            }
        }
        
        return ans;
    }
}