LeetCode 热题 100：03 最长连续序列

题目描述

力扣第128题「最长连续序列」要求如下：给定一个未排序的整数数组 nums，返回最长连续元素序列的长度。要求算法的时间复杂度为 O(n)。

示例 1：

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

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

解法

解法一：哈希表

使用哈希表存储每个元素，遍历数组中的每个元素，对于每个元素以其为起点，向上查找连续的数字，同时更新最长连续序列的长度。

时间复杂度：O(N)，其中 N 为数组长度。虽然看起来是两层循环，但是每个数字最多被访问两次。
空间复杂度：O(N)，存储数组元素到哈希表。

代码示例：

1. 创建一个哈希表 numSet，将数组 nums 中的所有元素添加到 numSet 中。
2. 初始化最长连续序列长度 longestStreak 为 0。
3. 遍历 numSet 中的每个元素 num。
4. 如果 numSet 中不存在 num - 1，则 num 是连续序列的起点。从 num 开始向上寻找连续的数字，同时更新当前连续序列的长度 currentStreak。
5. 比较并更新最长连续序列长度 longestStreak。
6. 遍历结束后，longestStreak 即为最长连续序列的长度。

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

public class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        
        int longestStreak = 0;
        
        for (int num : numSet) {
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                
                while (numSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        
        return longestStreak;
    }
}

解决的问题场景

「最长连续序列」可以应用于：

• 数据库中查询连续出现的记录。
• 游戏中寻找玩家的最长连胜记录。
• 时间序列分析中寻找连续事件。

考察的知识点

• 哈希表的使用。
• 数组的遍历。
• 复杂度分析。

相似题目推荐

• 数组中的第K个最大元素（LeetCode Problem #215: Kth Largest Element in an Array）
• 合并区间（LeetCode Problem #56: Merge Intervals）

总结与建议

「最长连续序列」是一道经典的哈希表应用题目，主要考察对哈希表操作以及复杂度分析的能力。这道题的关键在于理解如何利用哈希表的 O(1) 时间复杂度特性来快速检查元素的存在性。对于希望提升算法水平的开发者来说，这道题目是一个很好的练习，因为它要求在保证时间复杂度的情况下，找到一种有效的方法解决问题。在实际应用中，了解如何处理和优化连续性问题也是非常有用的。