用Java实现O(n)时间复杂度查找最长连续序列

问题描述

128. 最长连续序列

方法思路

核心思想

通过**哈希集合（HashSet）**存储所有元素，快速判断某个数字是否存在，从而避免暴力遍历。关键点在于：仅处理连续序列的起点元素，以减少不必要的重复计算。

步骤详解

1. 哈希集合存储元素
   将所有元素存入哈希集合，使得查询元素是否存在的时间复杂度为 O(1)。

2. 寻找连续序列的起点
   遍历元素时，若当前元素的前一个数（即 num-1）不存在于集合中，则说明当前元素是一个连续序列的起点。

3. 扩展连续序列
   从起点元素开始，依次检查后续连续的数字（num+1、num+2…）是否存在，并统计序列长度。

4. 维护最大长度
   每次找到一个连续序列后，更新记录的最大长度。

代码实现

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        
        int maxLength = 0;
        
        for (int num : numSet) {
            // 仅处理连续序列的起点
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                
                // 向后扩展序列
                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }
                
                maxLength = Math.max(maxLength, currentStreak);
            }
        }
        
        return maxLength;
    }
}

代码解析

1. 初始化哈希集合

   Set<Integer> numSet = new HashSet<>();
   for (int num : nums) {
       numSet.add(num);
   }
   

   • 将数组元素存入哈希集合，去重并支持 O(1) 时间的查询。

2. 遍历哈希集合

   for (int num : numSet) {
       if (!numSet.contains(num - 1)) {
           // 处理逻辑
       }
   }
   

   • 遍历哈希集合而非原数组，避免处理重复元素。

3. 起点判断与序列扩展

   if (!numSet.contains(num - 1)) {
       int currentNum = num;
       int currentStreak = 1;
       while (numSet.contains(currentNum + 1)) {
           currentNum++;
           currentStreak++;
       }
       maxLength = Math.max(maxLength, currentStreak);
   }
   

   • 若当前元素是起点，则向后扩展序列，统计长度。

时间复杂度分析

• 哈希集合构建：O(n)
  遍历数组一次，将元素存入集合。

• 遍历与扩展序列：O(n)
  每个元素最多被访问两次：一次在哈希集合遍历中，一次在扩展序列时。

总时间复杂度为 O(n)，满足要求。

常见问题

Q1：为什么要遍历哈希集合而不是原数组？

• 去重优化：哈希集合已去重，避免重复处理相同元素。
• 无序性无关：无论遍历顺序如何，算法的核心逻辑不受影响。

Q2：如何处理重复元素？

哈希集合自动去重，遍历时每个元素仅处理一次。

Q3：为何要判断 num-1 是否存在？

确保仅处理连续序列的起点，避免重复计算。例如，若 num-1 存在，则 num 一定不是某个序列的起点。

优化拓展

遍历原数组的优化方法

若强制遍历原数组，需解决重复元素问题。可以通过记录已访问元素来避免重复处理：

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) numSet.add(num);
        
        Set<Integer> visited = new HashSet<>(); // 记录已处理的元素
        int maxLength = 0;
        
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (visited.contains(num)) continue; // 跳过已处理的元素
            
            visited.add(num);
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                    visited.add(currentNum); // 标记后续元素为已处理
                }
                maxLength = Math.max(maxLength, currentStreak);
            }
        }
        return maxLength;
    }
}

• 缺点：需要额外的空间存储 visited 集合。

总结

通过哈希集合和仅处理连续序列起点，算法在 O(n) 时间内高效解决问题。核心在于避免重复遍历和冗余计算。此方法在面试中常见，建议熟练掌握。