LeetCode128 最长连续序列

LeetCode128 最长连续序列

在这篇博客中，我们将讨论如何设计并实现一个时间复杂度为 O(n) 的算法来解决给定未排序整数数组的最长连续序列问题。问题的描述如下：

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

解决方案

算法思路

我们可以使用哈希集合（unordered_set）来快速检查数组中是否存在某个元素。首先，将数组中的所有元素添加到哈希集合中。然后，遍历数组中的每个元素，对于每个元素，检查它是否是连续序列的起点。如果是起点，我们就开始向后查找，直到找不到连续的元素为止。在此过程中，我们更新最长连续序列的长度。

代码实现

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

using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> uset(nums.begin(), nums.end());
        int max_length = 0;
        for(auto num : uset){
            if(!uset.count(num - 1)){
                int current_num = num + 1;
                while(uset.count(current_num)) {
                    current_num++;
                }
                max_length = max(max_length, current_num - num);
            }
        }
        return max_length;
    }
};

时间复杂度分析

该算法的关键在于使用哈希集合快速查找元素，因此时间复杂度为 O(n)。在遍历数组时，对于每个元素，我们至多执行两次哈希集合的查找操作，因此总体时间复杂度为 O(n)。

结论

通过使用哈希集合，我们成功设计了一个时间复杂度为 O(n) 的算法来解决未排序整数数组的最长连续序列问题。该算法的核心思想是通过检查每个元素是否是连续序列的起点，从而避免了不必要的遍历操作，实现了高效的解决方案。