128. Longest Consecutive Sequence

Hash

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int maxLength = 0;
        for (int num : nums) {
            if (set.contains(num - 1)) {
                // 当前 num 不是序列起始数字，无需重复统计
                continue;
            }

            int length = 1;
            for (int i = num + 1; set.contains(i); i++) {
                length++;
            }
            maxLength = Math.max(maxLength, length);
        }
        
        return maxLength;
    }
}

UnionFind

class Solution {
    private static class UnionFind {
        private final int[] parent;
        private final int[] size;

        public UnionFind(int count) {
            this.parent = new int[count];
            for (int i = 0; i < count; i++) {
                parent[i] = i;
            }
            this.size = new int[count];
            Arrays.fill(size, 1);
        }

        public int getRoot(int x) {
            if (x != parent[x]) {
                x = getRoot(parent[x]); // path compression
            }
            return x;
        }

        public void union(int x, int y) {
            int xRoot = getRoot(x);
            int yRoot = getRoot(y);
            if (xRoot == yRoot) {
                return;
            }

            parent[xRoot] = yRoot;
            size[yRoot] += size[xRoot];
        }
    }

    public int longestConsecutive(int[] nums) {
        UnionFind unionFind = new UnionFind(nums.length); // 存储索引

        Map<Integer, Integer> valueToIndexMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (valueToIndexMap.containsKey(nums[i])) {
                continue; // 不处理重复数字
            }
            valueToIndexMap.put(nums[i], i);
            Integer index = valueToIndexMap.get(nums[i] - 1);
            if (index != null) {
                unionFind.union(i, index);
            }
            index = valueToIndexMap.get(nums[i] + 1);
            if (index != null) {
                unionFind.union(i, index);
            }
        }

        int maxLength = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i == unionFind.getRoot(i)) {
                maxLength = Math.max(maxLength, unionFind.size[i]);
            }
        }

        return maxLength;
    }
}

Reference

128. Longest Consecutive Sequence