当前位置：首页 > article >正文

力扣HOT100之哈希：128. 最长连续序列

article 2025/3/10 18:35:58

这道题我想的比较简单，先遍历一遍输入的数组，然后将读取到的数字存入一个map容器中（注意，不是unordered_map），数字作为键，布尔变量为值，然后再遍历一遍map，用一个变量temp记录上次循环读取到的值，temp_result用来记录当前遍历到的子序列的长度，一旦遇到当前遍历到的值与上一次遍历到的值不连续的情况，立马将temp_result置为1，然后继续向后遍历，在每次循环中，最终返回的值result与temp_result比较大小，将较大值作为result的新值。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int result = 0;
        map<int, bool> hash;
        for(int& i : nums)
            hash[i] = true;
        int temp;
        int temp_result = 0;
        for(auto it = hash.begin(); it != hash.end(); it++){
            if(it == hash.begin()){
                temp_result++;
            }
            else{
                if(temp == it -> first - 1)
                    temp_result++;
                else{
                    temp_result = 1;
                }
            }
            temp = it -> first;
            result = max(result, temp_result);
            cout << it -> first << endl;
        }
        return result;
    }
};

果不其然，通过是通过了，但是耗时太长了，不符合O(n)的时间复杂度要求，后面看了下灵茶山大佬的题解，重新做一遍。
先说下主要原理：先利用unordered_set构建哈希表，然后遍历哈希表中的每一个元素，当遍历到一个元素时，先判断当前元素的上一个元素是否在哈希表中，如果在，就直接跳过本次循环，开启下一次循环，当出现当前元素的上一个元素不在哈希表中时，说明上一段连续的学列已经遍历结束，开启一段新的序列，此时不再跳过循环，而是定义一个循环，在循环内不断查找从当前元素起的最长连续序列，当该循环结束时意味着当前元素为起点的连续序列已经查找完毕，将最后一个元素的数值减去当前元素的值即为当前元素为起点的连续序列长度，再将该长度与之前保存的最长连续子序列的长度作比较，取较大值为新的最长连续子序列的长度。由于哈希表的查找耗时为O(1)，虽然代码中写的是一个类似二重循环的结构，但是这个二重循环在大多数情况下会退化为一重循环，经历若干次查找，时间复杂度为O(n)。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int result = 0;
        unordered_set<int> hash(nums.begin(), nums.end());  //通过集合来构建哈希表
        for(const int& i : hash){
            if(hash.find(i - 1) != hash.end())  //确保当前遍历到的元素和上一个元素是连续的
                continue;
            //以下是当前元素与上一个元素不连续的情况
            int j = i + 1;
            while(hash.find(j) != hash.end())   //该循环用于寻找从当前元素起的连续元素个数
                j++;
            result = max(result, j - i);
        }
        return result;
    }
};