128. 最长连续序列

题目：最长连续序列

描述：

给定一个未排序的整数数组 nums，找出数字连续的最长序列的长度。不要求序列元素在原数组中连续。

---

示例：

示例 1:

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

示例 2:

输入: nums = [0, 1, 2, 3, 4, 5]
输出: 6

---

解题思路：

为了找到最长的连续序列，我们可以利用 哈希集合 (HashSet) 来高效地进行查找。通过哈希集合，我们可以将数组中的所有元素存储起来，从而能在常数时间内检查某个元素是否存在。

步骤：

1. 将数组中的所有元素存入哈希集合 set。
2. 遍历数组中的每个元素 num，对于每个元素，检查它是否是一个连续序列的起点。一个元素是连续序列的起点，当且仅当 num-1 不在集合中。
3. 如果是起点，从该元素开始，继续检查 num+1, num+2，直到没有连续的元素为止，并更新最长的序列长度。
4. 遍历完成后，返回最长连续序列的长度。

代码实现：

import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        Solution solution = new Solution();
        int result = solution.longestConsecutive(nums);

        // 输出结果
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int longestConsecutive(int[] nums) {
        // 创建一个哈希集合来存储所有元素
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int longestStreak = 0;

        // 遍历每个元素
        for (int num : nums) {
            // 如果 num-1 不在集合中，那么 num 是一个可能的连续序列的起点
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                // 向后查找连续的数字
                while (set.contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }

                // 更新最长连续序列的长度
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}

---

时间复杂度分析：

• 时间复杂度：O(n)，其中 n 是数组的长度。遍历数组中的每个元素，且每个元素最多只会被访问两次（一次是检查是否是序列起点，一次是进行连续性查找）。
• 空间复杂度：O(n)，我们使用了一个哈希集合来存储数组中的所有元素。

---

总结：

通过哈希集合存储所有元素，并结合元素是否为连续序列的起点，我们可以在 O(n) 时间内找到最长的连续序列。该方法非常高效，适合解决中等规模的数据集。