longest-consecutive-sequence

https://leetcode.com/problems/longest-consecutive-sequence/

最长连续序列

function longestConsecutive(nums: number[]): number {
    if (nums.length === 0) return 0;
    
    // 创建一个 Set 用于 O(1) 查找
    const numSet = new Set(nums);
    let maxLength = 0;
    
    for (const num of numSet) {
        // 只有当 num-1 不存在时，才开始计数
        // 这确保我们只从序列的起始数字开始计算
        if (!numSet.has(num - 1)) {
            let currentNum = num;
            let currentLength = 1;
            
            // 继续查找连续的数字
            while (numSet.has(currentNum + 1)) {
                currentNum++;
                currentLength++;
            }
            
            maxLength = Math.max(maxLength, currentLength);
        }
    }
    
    return maxLength;
}

复杂度分析

• 时间复杂度：O(n)
  • 虽然有嵌套循环，但每个数字最多被访问两次
  • Set 的创建需要 O(n)
  • 查找操作 O(1)
• 空间复杂度：O(n)
  • 需要一个 Set 存储所有数字

测试用例

console.log(longestConsecutive([100,4,200,1,3,2]));     // 预期输出: 4
console.log(longestConsecutive([0,3,7,2,5,8,4,6,0,1])); // 预期输出: 9
console.log(longestConsecutive([]));                     // 预期输出: 0
console.log(longestConsecutive([1]));                    // 预期输出: 1
console.log(longestConsecutive([1,2,0,1]));             // 预期输出: 3

实现思路

这个解决方案巧妙地结合了数组和哈希表（Set）的概念：

1. 使用 Set 数据结构存储所有数字，实现 O(1) 的查找效率
2. 通过检查 num-1 是否存在，确保只从序列的起始数字开始计数
3. 对于每个起始数字，向后查找连续的数字序列
4. 维护最长序列的长度

关键优化点是使用 Set 而不是数组来存储数字，这样可以将查找操作的时间复杂度从 O(n) 降低到 O(1)。