LeetCode 补拙笔记

0. 前言

• 日期：2026.06.07
• 题目：128. 最长连续序列
• 难度：中等
• 标签：数组、哈希表

1. 题目理解

问题描述： 给定一个未排序的整数数组，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

• 要求实现时间复杂度为 $O(n)$ 的算法。

示例：

输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]，长度为 4。

2. 解题思路

核心观察

• 暴力排序法的时间复杂度为 $O(n\log n)$，不符合要求。
• 利用哈希表实现 $O(1)$ 级别的查询，将整体复杂度降至 $O(n)$。
• 关键技巧：只从序列的起始点（即 num-1 不存在的数）开始遍历，避免重复计算。

算法步骤

1. 将所有数字存入哈希集合；
2. 遍历每个数字，判断其是否为序列的起始点；
3. 若是起始点，则向后查找连续序列的长度；
4. 更新全局最长序列长度。

3. 代码实现

package lc100_lc199.lc128;

import java.util.HashMap;

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        int res = 1;
        for (int num : nums) {
            if (!map.containsKey(num)) {
                int left = map.getOrDefault(num - 1, 0);
                int right = map.getOrDefault(num + 1, 0);
                int len = left + right + 1;
                map.put(num, len);
                map.put(num - left, len);
                map.put(num + right, len);
                res = Math.max(res, len);
            }
        }
        return res;
    }
}

4. 代码优化说明

class Solution {
public int longestConsecutive(int[] nums) {
int n = nums.length;
if (n < 2) return n;

        // 1. 找最小最大值，判断数据分布情况
        int min = nums[0], max = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] < min) min = nums[i];
            else if (nums[i] > max) max = nums[i];
        }
        long range = (long) max - min + 1;

        // 2. 密集数据：用布尔数组标记，查询O(1)，无哈希开销
        if (range <= n * 10L && range <= Integer.MAX_VALUE) {
            byte[] present = new byte[(int) range];
            for (int num : nums) {
                present[num - min] = 1;
            }
            int maxLen = 0, currLen = 0;
            for (byte b : present) {
                if (b == 1) {
                    currLen++;
                } else {
                    maxLen = Math.max(maxLen, currLen);
                    currLen = 0;
                }
            }
            return Math.max(maxLen, currLen);
        }

        // 3. 稀疏数据：用开放寻址哈希表，比HashMap更快
        int capacity = 2;
        while (capacity < n * 2) capacity <<= 1;
        int mask = capacity - 1;
        int[] keys = new int[capacity];
        byte[] states = new byte[capacity]; // 0=空,1=占用

        int uniqueCount = 0;
        for (int num : nums) {
            int idx = (num & mask); // 直接用低位哈希
            while (states[idx] == 1) {
                if (keys[idx] == num) break;
                idx = (idx + 1) & mask;
            }
            if (states[idx] == 0) {
                states[idx] = 1;
                keys[idx] = num;
                nums[uniqueCount++] = num; // 覆盖原数组存去重值
            }
        }

        int maxLen = 0;
        for (int i = 0; i < uniqueCount; i++) {
            int num = nums[i];
            // 只从连续序列的最小值开始
            if (!contains(keys, states, mask, num - 1)) {
                int len = 1;
                while (contains(keys, states, mask, num + len)) {
                    len++;
                }
                maxLen = Math.max(maxLen, len);
                if (maxLen > uniqueCount / 2) return maxLen; // 剪枝
            }
        }
        return maxLen;
    }

    private boolean contains(int[] keys, byte[] states, int mask, int num) {
        int idx = (num & mask);
        while (states[idx] == 1) {
            if (keys[idx] == num) return true;
            idx = (idx + 1) & mask;
        }
        return false;
    }
}

5. 复杂度分析

• 基础哈希表解法
  • 时间复杂度：$O(n)$，每个元素最多被访问两次（一次存入，一次遍历序列）。
  • 空间复杂度：$O(n)$，哈希集合存储所有元素。
• 优化版（分情况处理）
  • 时间复杂度：平均 $O(n)$，根据数据分布自动选择最优方案（布尔数组/开放寻址哈希表）。
  • 空间复杂度：$O(n)$，但实际开销比 HashSet 更低。

6. 总结

• 核心思路：利用哈希表的 $O(1)$ 查询实现线性时间复杂度。
• 优化亮点：
  1. 分情况处理：根据数据密集度选择布尔数组或哈希表，减少不必要的哈希开销。
  2. 开放寻址哈希表：比 HashMap 更快，减少了自动装箱/拆箱的开销。
  3. 剪枝优化：当找到的序列长度超过数组一半时，直接返回，无需继续遍历。
• 关键技巧：只从序列的起始点开始遍历，避免重复计算，保证了 $O(n)$ 的时间复杂度。