LeetCode LCR 119. 最长连续序列

Categories:

题目描述
思路分析
1. 解法一：哈希集合 + 序列起点剪枝（推荐）
2. 解法二：并查集
相似题目

题目描述

✅ LCR 119. 最长连续序列

思路分析

解法一：哈希集合 + 序列起点剪枝（推荐）

核心思路：

暴力做法对每个数向右扩展查找 num+1, num+2, ...，时间复杂度 O(n²)。

关键优化：只从连续序列的起点开始向右扩展。若 num - 1 已存在于集合中，说明 num 不是起点，直接跳过。

只有当 num - 1 不在集合中时，num 才是一段连续序列的起点，此时才触发向右扩展统计长度。

将所有数存入 HashSet 实现 O(1) 查询，同时天然去重。

为什么时间复杂度是 O(n)：

外层遍历 n 个数，但内层 while 只对起点触发。

每个数至多被扩展一次（每个数只属于一条连续序列），两层合计操作次数为 n，均摊 O(1)。

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，每个元素至多被处理一次

空间复杂度：O(n)，HashSet 存储所有不重复的数

class Solution {
    public int longestConsecutive(int[] nums) {
        // 将所有数存入哈希集合，实现 O(1) 查询并去重
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int maxLen = 0;
        for (int num : set) {
            // 只从序列起点开始扩展，跳过非起点
            if (!set.contains(num - 1)) {
                int cur = num;
                int len = 1;
                // 向右连续扩展，统计序列长度
                while (set.contains(cur + 1)) {
                    cur++;
                    len++;
                }
                maxLen = Math.max(maxLen, len);
            }
        }
        return maxLen;
    }
}

func longestConsecutive(nums []int) int {
    // 将所有数存入哈希集合，实现 O(1) 查询并去重
    numSet := make(map[int]bool)
    for _, num := range nums {
        numSet[num] = true
    }
    maxLen := 0
    for num := range numSet {
        // 只从序列起点开始扩展，跳过非起点
        if !numSet[num-1] {
            curNum := num
            curLen := 1
            // 向右连续扩展，统计序列长度
            for numSet[curNum+1] {
                curNum++
                curLen++
            }
            if curLen > maxLen {
                maxLen = curLen
            }
        }
    }
    return maxLen
}

解法二：并查集

核心思路：

将每个数初始化为独立的集合，父节点指向自身。

遍历数组，若 num + 1 也在数组中，则将 num 与 num + 1 合并到同一集合。

合并时同步维护每个根节点对应集合的大小，合并完成后所有集合大小的最大值即为答案。

并查集适合动态合并场景，此题中哈希集合解法更简洁，并查集作为扩展了解。

复杂度分析：

时间复杂度：O(n·α(n))，其中 n 为数组长度，α 为反阿克曼函数，近似 O(n)

空间复杂度：O(n)，并查集存储 n 个节点的父节点与大小信息

class Solution {
    // 父节点数组
    private int[] parent;
    // 每个集合的大小
    private int[] size;

    public int longestConsecutive(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        // 建立数值到下标的映射
        Map<Integer, Integer> indexMap = new HashMap<>();
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            // 去重：同一数值只保留第一次出现
            if (indexMap.containsKey(nums[i])) {
                continue;
            }
            indexMap.put(nums[i], i);
            parent[i] = i;
            size[i] = 1;
        }
        // 遍历每个数，尝试与 num+1 合并
        for (int num : indexMap.keySet()) {
            if (indexMap.containsKey(num + 1)) {
                union(indexMap.get(num), indexMap.get(num + 1));
            }
        }
        // 统计最大集合大小
        int maxLen = 0;
        for (int num : indexMap.keySet()) {
            int idx = indexMap.get(num);
            maxLen = Math.max(maxLen, size[find(idx)]);
        }
        return maxLen;
    }

    private int find(int x) {
        // 路径压缩
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    private void union(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (px == py) {
            return;
        }
        // 按秩合并，小集合并入大集合
        if (size[px] < size[py]) {
            parent[px] = py;
            size[py] += size[px];
        } else {
            parent[py] = px;
            size[px] += size[py];
        }
    }
}

type UnionFind struct {
    parent []int
    size   []int
}

func newUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    size := make([]int, n)
    for i := range parent {
        parent[i] = i
        size[i] = 1
    }
    return &UnionFind{parent: parent, size: size}
}

func (uf *UnionFind) find(x int) int {
    // 路径压缩
    if uf.parent[x] != x {
        uf.parent[x] = uf.find(uf.parent[x])
    }
    return uf.parent[x]
}

func (uf *UnionFind) union(x, y int) {
    px, py := uf.find(x), uf.find(y)
    if px == py {
        return
    }
    // 按秩合并，小集合并入大集合
    if uf.size[px] < uf.size[py] {
        uf.parent[px] = py
        uf.size[py] += uf.size[px]
    } else {
        uf.parent[py] = px
        uf.size[px] += uf.size[py]
    }
}

func longestConsecutive(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    // 建立数值到下标的映射，同时去重
    indexMap := make(map[int]int)
    uf := newUnionFind(n)
    for i, num := range nums {
        if _, exists := indexMap[num]; exists {
            continue
        }
        indexMap[num] = i
    }
    // 遍历每个数，尝试与 num+1 合并
    for num, idx := range indexMap {
        if nextIdx, exists := indexMap[num+1]; exists {
            uf.union(idx, nextIdx)
        }
    }
    // 统计最大集合大小
    maxLen := 0
    for _, idx := range indexMap {
        if s := uf.size[uf.find(idx)]; s > maxLen {
            maxLen = s
        }
    }
    return maxLen
}

相似题目

题目	难度	考察点
674. 最长连续递增序列	简单	贪心，有序连续
300. 最长递增子序列	中等	动态规划、二分
298. 二叉树最长连续序列	中等	树上 DFS
549. 二叉树中最长的连续序列	中等	树上 DFS
2274. 不含特殊楼层的最大连续楼层数	中等	排序、连续区间
1004. 最大连续1的个数 III	中等	滑动窗口
485. 最大连续 1 的个数	简单	数组遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/98441463