给定一个未排序的整数数组 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

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109

要解决这个问题，我们可以利用哈希集合（unordered_set）来存储数组中的元素，以便在 O(1) 时间内查找是否存在某个数字。通过这种方式，我们可以避免使用嵌套循环，从而实现 O(n) 的时间复杂度。

算法步骤

1. 存储元素：将所有元素插入到一个哈希集合中。
2. 查找序列：遍历每个元素，检查它是否是序列的起始元素（即 num - 1 不在集合中）。
3. 扩展序列：如果是起始元素，则从该元素开始，向上查找连续的数字，直到找不到为止，记录当前序列的长度。
4. 更新最大长度：在每次找到一个新序列后，更新最大长度。

C++ 实现

下面是实现上述算法的 C++ 代码：

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

int longestConsecutive(vector<int>& nums) {
    // 使用 unordered_set 存储元素
    unordered_set<int> numSet(nums.begin(), nums.end());
    int longestStreak = 0;

    // 遍历每个数字
    for (int num : numSet) {
        // 只从序列的起始元素开始查找
        if (numSet.find(num - 1) == numSet.end()) {
            int currentNum = num;
            int currentStreak = 1;

            // 向上查找连续的数字
            while (numSet.find(currentNum + 1) != numSet.end()) {
                currentNum++;
                currentStreak++;
            }

            // 更新最长序列长度
            longestStreak = max(longestStreak, currentStreak);
        }
    }

    return longestStreak;
}

int main() {
    vector<int> nums1 = {100, 4, 200, 1, 3, 2};
    cout << "Longest consecutive sequence length: " << longestConsecutive(nums1) << endl; // 输出 4

    vector<int> nums2 = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
    cout << "Longest consecutive sequence length: " << longestConsecutive(nums2) << endl; // 输出 9

    return 0;
}

代码说明

1. 输入和输出：

   • longestConsecutive 函数接收一个整数向量 nums，返回最长连续序列的长度。
   • 在 main 函数中，我们测试了两个示例用例。

2. 哈希集合：

   • 我们使用 unordered_set<int> 来存储数组中的元素，以便快速查找。

3. 查找逻辑：

   • 对于每个元素，如果它的前一个元素不在集合中，则它是一个新序列的起始元素。
   • 然后我们通过一个 while 循环来查找所有连续的数字，并更新当前序列的长度。

4. 性能：

   • 整个算法的时间复杂度为 O(n)，因为每个元素最多被访问两次（一次是插入，一次是查找）。

1. unordered_set<int> numSet(nums.begin(), nums.end());

解释

• unordered_set<int>：这是 C++ STL（标准模板库）提供的一个容器，用于存储唯一的元素，并且不保持任何特定的顺序。这里的 int 指定了集合中元素的类型为整数。

• nums.begin() 和 nums.end()：

  • nums 是一个 vector 或数组，begin() 返回一个指向数组第一个元素的迭代器，而 end() 返回一个指向数组最后一个元素后一个位置的迭代器。

• 这个构造函数的作用：unordered_set<int> numSet(nums.begin(), nums.end()); 使用 nums 中的所有元素初始化一个 unordered_set<int>。这意味着 numSet 将包含 nums 中的所有整数，且只保留唯一值，重复的值将被忽略。

示例

假设 nums 是以下数组：

vector<int> nums = {1, 2, 2, 3, 4, 4, 5};

那么构造 numSet 之后，它将包含 {1, 2, 3, 4, 5} 五个元素。

这段代码的目的是查找给定数字 num 在一个集合 numSet 中是否能够形成一个连续的数字序列。如果能够，它会计算出这个序列的长度。

逐行解释

1. 检查前一个数字是否存在：

   if (numSet.find(num - 1) == numSet.end()) {
   

   • numSet.find(num - 1)：尝试在 numSet 中查找 num - 1，即当前数字的前一个数字。
   • numSet.end()：返回一个迭代器，表示 numSet 的结束位置。如果 find 返回的迭代器等于 end()，表示未找到 num - 1。
   • 条件的意义：这个条件判断 num 是否是一个连续序列的起始数字。如果 num - 1 不在集合中，说明 num 没有前驱，因此它是一个新序列的开始。

2. 初始化当前数字和当前序列长度：

   int currentNum = num;
   int currentStreak = 1;
   

   • currentNum：设置为当前数字 num，用于跟踪当前连续序列中的数字。
   • currentStreak：初始化为 1，表示当前序列的长度从 num 开始，初始长度为 1。

3. 向上查找连续的数字：

   while (numSet.find(currentNum + 1) != numSet.end()) {
       currentNum++;
       currentStreak++;
   }
   

   • while 循环：这个循环的目的是查找当前数字 currentNum 的下一个数字（currentNum + 1）是否存在于 numSet 中。
   • numSet.find(currentNum + 1) != numSet.end()：如果 currentNum + 1 存在于集合中，说明我们可以继续扩展当前的连续序列。
   • 循环体：
     • currentNum++：将 currentNum 增加 1，以检查下一个数字。
     • currentStreak++：如果找到了下一个连续数字，增加当前序列的长度 currentStreak。

逻辑总结

• 这段代码的主要目的是从一个被认为是连续序列起始位置的数字开始，向上查找所有连续的数字，并统计它们的数量。
• 通过这种方式，可以有效地找到以 num 开始的最长连续序列的长度。

整体流程示例

假设 numSet 包含以下数字：{100, 4, 200, 1, 3, 2}，并且当前遍历到的 num 是 1。

1. 检查 0：

   • numSet.find(0) 返回 end()，说明 0 不在集合中。
   • 因此，1 是连续序列的起始数字。

2. 初始化：

   • currentNum 被设置为 1，currentStreak 被设置为 1。

3. 查找连续数字：

   • 查找 2：numSet.find(2) 找到 2，currentNum 增加到 2，currentStreak 增加到 2。
   • 查找 3：numSet.find(3) 找到 3，currentNum 增加到 3，currentStreak 增加到 3。
   • 查找 4：numSet.find(4) 找到 4，currentNum 增加到 4，currentStreak 增加到 4。
   • 查找 5：numSet.find(5) 未找到，循环结束。

最终，currentStreak 的值为 4，表示从 1 开始的最长连续序列是 1, 2, 3, 4，长度为 4。

要解决这个问题，我们可以使用哈希表（在 C 语言中可以使用 unordered_set 的结构）来存储数组中的元素。通过这种方式，我们可以在 O(1) 的时间复杂度内检查某个数字是否存在。下面是具体的步骤和 C 语言实现。

C 语言实现

下面是 C 语言的实现代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct HashSet {
    int *data;
    int size;
    int capacity;
} HashSet;

// 创建一个哈希表
HashSet* createHashSet(int capacity) {
    HashSet *set = (HashSet *)malloc(sizeof(HashSet));
    set->data = (int *)calloc(capacity, sizeof(int));
    set->size = 0;
    set->capacity = capacity;
    return set;
}

// 哈希函数
int hash(int key, int capacity) {
    return (key % capacity + capacity) % capacity; // 处理负数
}

// 插入元素到哈希表
void insert(HashSet *set, int key) {
    int index = hash(key, set->capacity);
    while (set->data[index] != 0) {
        index = (index + 1) % set->capacity; // 线性探测
    }
    set->data[index] = key;
    set->size++;
}

// 查找元素是否在哈希表中
int contains(HashSet *set, int key) {
    int index = hash(key, set->capacity);
    while (set->data[index] != 0) {
        if (set->data[index] == key) {
            return 1; // 找到
        }
        index = (index + 1) % set->capacity; // 线性探测
    }
    return 0; // 未找到
}

// 释放哈希表
void freeHashSet(HashSet *set) {
    free(set->data);
    free(set);
}

// 主函数：查找最长连续序列
int longestConsecutive(int* nums, int numsSize) {
    if (numsSize == 0) return 0;

    // 创建哈希表
    HashSet *set = createHashSet(numsSize);
    
    // 将所有数字插入哈希表
    for (int i = 0; i < numsSize; i++) {
        insert(set, nums[i]);
    }

    int longestStreak = 0;

    // 查找最长连续序列
    for (int i = 0; i < numsSize; i++) {
        int num = nums[i];
        // 只从序列的起始元素开始查找
        if (!contains(set, num - 1)) {
            int currentNum = num;
            int currentStreak = 1;

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

            // 更新最长序列长度
            if (currentStreak > longestStreak) {
                longestStreak = currentStreak;
            }
        }
    }

    // 释放哈希表
    freeHashSet(set);
    return longestStreak;
}

// 测试代码
int main() {
    int nums1[] = {100, 4, 200, 1, 3, 2};
    int length1 = sizeof(nums1) / sizeof(nums1[0]);
    printf("Longest consecutive sequence length: %d\n", longestConsecutive(nums1, length1)); // 输出 4

    int nums2[] = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
    int length2 = sizeof(nums2) / sizeof(nums2[0]);
    printf("Longest consecutive sequence length: %d\n", longestConsecutive(nums2, length2)); // 输出 9

    return 0;
}

代码说明

• 哈希表实现：我们定义了一个简单的哈希表结构 HashSet，包括动态数组 data 和相关的大小及容量。
• 插入与查找：使用线性探测法来处理哈希冲突。
• longestConsecutive 函数：实现了查找最长连续序列的逻辑。
• 测试用例：在 main 函数中，我们提供了两个示例，验证算法的正确性。

时间和空间复杂度

• 时间复杂度：O(n)，因为我们遍历了数组并且哈希表的查找和插入平均都是 O(1)。
• 空间复杂度：O(n)，用于存储哈希表中的元素。

总结

这种方法有效地利用了哈希集合的特性，能够在 O(n) 的时间复杂度内找到最长的连续序列，是解决此类问题的高效方案。