【LeetCode 热题 100】128. 最长连续序列

Problem: 128. 最长连续序列

整体思路

这段代码的目的是高效地解决 “最长连续序列” 问题。具体来说，它需要在一个未排序的整数数组 nums 中，找出由连续整数构成的最长序列的长度。例如，对于输入 [100, 4, 200, 1, 3, 2]，最长的连续序列是 [1, 2, 3, 4]，其长度为 4。

算法的整体思路可以分解为以下几个核心步骤：

1. 数据结构选择与预处理：

   • 代码首先将输入的数组 nums 转换成一个哈希集合 (HashSet) nS。这个选择是算法效率的关键。
   • 目的：哈希集合提供了平均时间复杂度为 O(1) 的元素查找操作 (contains)，这远快于在数组中查找的 O(N) 效率。同时，集合也自动处理了输入中的重复元素。

2. 遍历与序列起点识别：

   • 代码接着遍历哈希集合中的每一个数字 x。
   • 对于每个数字，它会执行一个至关重要的判断：if (!nS.contains(x - 1))。
   • 目的：这个判断是为了找到一个连续序列的 “起点”。如果一个数字 x 的前一个数 x - 1 不在集合中，那么 x 就是一个潜在连续序列的开始。这个优化避免了对同一个序列的重复计算。例如，在序列 1, 2, 3, 4 中，当遍历到 2、3 或 4 时，它们的前一个数都在集合里，因此会跳过计算，只有当遍历到 1 时，才会启动真正的序列长度计算。

3. 序列长度计算：

   • 一旦确定了一个序列的起点 x，代码会进入一个 while 循环。
   • 这个循环会不断检查当前数字的下一个数 (cur + 1) 是否存在于哈希集合中。
   • 如果存在，就将当前序列的长度 len 加一，并将当前数字 cur 更新为下一个数，持续这个过程直到序列中断。

4. 结果更新与返回：

   • 当一个连续序列的探测结束后（即 while 循环终止），代码会用 Math.max(ans, len) 来更新全局的最长序列长度 ans。
   • 在遍历完哈希集合中的所有数字后，ans 中存储的就是最终的结果，将其返回。

总而言之，该算法通过将列表转换为哈希集合来优化查找效率，并通过只从序列的起点开始计数来避免冗余工作，从而实现线性时间复杂度的解决方案。

完整代码

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

class Solution {
    /**
     * 找到一个未排序的整数数组中，最长连续序列的长度。
     * @param nums 整数数组
     * @return 最长连续序列的长度
     */
    public int longestConsecutive(int[] nums) {
        // nS: 创建一个哈希集合，用于存储数组中的所有唯一元素。
        // 主要优点是 O(1) 的平均查找时间复杂度和自动去重。
        Set<Integer> nS = new HashSet<>();
        // 步骤 1: 将所有元素添加到哈希集合中进行预处理。
        for (int num : nums) {
            nS.add(num);
        }
        
        // ans: 用于存储最终结果，即找到的最长连续序列的长度，初始化为0。
        int ans = 0;
        
        // 步骤 2: 遍历集合中的每一个唯一的数字。
        for (int x : nS) {
            // 这是算法的核心优化：检查 x-1 是否存在。
            // 如果不存在，说明 x 是一个连续序列的起点。
            // 这避免了对同一个序列的重复计算（例如，对于序列1,2,3,4，只有当x=1时，内部循环才会执行）。
            if (!nS.contains(x - 1)) {
                // 将当前数字 x 作为当前连续序列的起点。
                int cur = x;
                // 初始化当前连续序列的长度为 1（起点本身）。
                int len = 1;
                
                // 步骤 3: 从起点开始，向后查找连续的数字。
                // 只要当前数字的下一个数 (cur + 1) 存在于集合中，说明序列还在继续。
                while (nS.contains(cur + 1)) {
                    // 移动到序列中的下一个数字。
                    cur++;
                    // 增加当前连续序列的长度。
                    len++;
                }
                
                // 步骤 4: 在找到一个完整的序列后，更新全局最大长度。
                ans = Math.max(ans, len);
            } 
        }
        
        // 返回找到的最长长度。
        return ans;
    }
}

时空复杂度

时间复杂度：O(N)

1. 集合初始化：for (int num : nums) 循环将 N 个元素添加到 HashSet 中。HashSet 的 add 操作平均时间复杂度为 O(1)。因此，这部分的时间复杂度是 O(N)。
2. 主循环：for (int x : nS) 外层循环会遍历集合中的所有唯一元素。在最坏情况下（所有元素都唯一），循环会执行 N 次。
3. 内层循环：while (nS.contains(cur + 1)) 虽然这是一个嵌套循环，但由于 if (!nS.contains(x - 1)) 的判断，内层 while 循环只会对每个连续序列的 起始数字 执行。这意味着每个数字最多被访问两次：一次是在外层 for 循环中被检查，另一次是在内层 while 循环中作为序列的一部分被访问。
   • 所有 while 循环的总执行次数加起来最多也是 O(N) 级别。
   • 因此，两个循环加在一起的总复杂度是线性的。

综合分析：
整个算法的时间消耗主要由集合的初始化（O(N)）和循环遍历（O(N) + O(N) = O(N)）构成。因此，总的时间复杂度是 O(N)，其中 N 是输入数组 nums 的元素个数。

空间复杂度：O(N)

1. 主要存储开销：算法创建了一个哈希集合 nS 来存储输入数组 nums 中的所有唯一元素。
2. 最坏情况：当输入数组 nums 中的所有元素都是唯一的时候，nS 的大小将与 nums 的大小相同，即 N。
3. 其他变量：ans, cur, len 等变量都只占用常数级别的空间，即 O(1)。

综合分析：
算法所需的额外空间主要取决于哈希集合 nS 的大小。因此，空间复杂度为 O(N)，其中 N 是输入数组 nums 的元素个数。