128. 最长连续序列

class Solution {

    public int longestConsecutive(int[] nums) {
        int ans = 0;
        Set<Integer> set = new HashSet<>();
        for(int num : nums){
            set.add(num);
        }
        for(int num : set){
            // 如果set中存在num之前的一个数，说明当前num不是连续序列的开始
            if(set.contains(num-1))
                continue;
            int cur = num;
            // 此时num为一个连续序列的开始，现在才统计其所在连续序列长度
            // 在整个for循环中，此while循环总共走了n次，因为数组中的数只属于一个连续序列
            // 而我们每次只从连续序列的开始往后走
            while(set.contains(cur))
                cur++;
            ans = Math.max(cur-num, ans);
        }
        return ans;
    }
}

class Solution {

    public int longestConsecutive(int[] nums) {
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int num : nums){
            // 如果num不在任何已存在的区间
            if(!map.containsKey(num)){
                // 当前num不存在于区间，找到以num-1为结尾的连续区间的长度
                int lLen = map.getOrDefault(num-1, 0);
                // 找到以num+1为开始的连续区间的长度
                int rLen = map.getOrDefault(num+1, 0);
                // 加入num之后最新的区间长度
                int curLen = lLen + rLen + 1;
                ans = Math.max(ans, curLen);
                // num为区间[num-lLen, num+rLen]中的值，无论存什么值都无所谓
                // 因为在找区间的时候只会找到num所在的连续序列的左右端点
                map.put(num, -1);
                // 更新左端点开始连续序列的长度
                map.put(num-lLen, curLen);
                // 更新右端点结尾连续序列的长度
                map.put(num+rLen, curLen);
            }
        }
        return ans;
    }
}

class Solution {
    Map<Integer, Integer> parents = new HashMap<>();
    Map<Integer, Integer> count = new HashMap<>();

    // 带路径压缩的找上司
    public int find(int x){
        int p = parents.get(x);
        if(p == x)
            return p;
        // t为x的最终boss
        int t = find(p);
        // 直接将x的上司设置为t，将路径压缩
        parents.put(x, t);
        return t;
    }

    // 将x与y联合
    public void union(int x, int y){
        int p1 = find(x);
        int p2 = find(y);
        if(p1 == p2)
            return;
        // 若x与y的上司不是同一个人，则设置p2为p1的上司
        parents.put(p1, p2);
        // 此时p2手下的人数就为p1手下管理的人数加p2手下的人数
        count.put(p2, count.get(p1) + count.get(p2));
    }

    public int longestConsecutive(int[] nums) {
        int ans = 0;
        Set<Integer> set = new HashSet<>();
        // set去重，同时初始化parents和count
        for(int num : nums){
            parents.put(num, num);
            count.put(num, 1);
            set.add(num);
        }
        for(int num : set){
            if(set.contains(num-1))
                union(num, num-1);
            if(set.contains(num+1))
                union(num, num+1);
            // 查找num的最终boss的管理人数与当前ans相比，留最大
            ans = Math.max(ans, count.get(find(num)));
        }
        return ans;
    }
}