解析

哈希表

若使用双重循环来判断肯定没法达到O(n)的时间复杂度，可以考虑用哈希表来存储每个端点值对应连续区间的长度，关键是找到开始的端点值，只要找到开始的端点值，那么就可以往后遍历，直到找不到下一个端点值，这样就可以得到一个连续区间的长度，然后更新哈希表中的值，这样就可以在O(1)的时间复杂度内得到一个连续区间的长度。

//! n,n -> 遍历nums耗时；空间复杂度哈希表的存储
class Solution {
 public:
  int longestConsecutive(vector<int>& nums) {
    int res = 0;
    unordered_set<int> hashSet;
    for (int i = 0; i < nums.size(); ++i) {
      hashSet.insert(nums[i]);
    }

    for (auto e : hashSet) {
      int curNum = e; // e是不变量，无法修改
      if (!hashSet.count(curNum - 1)) {
        int nowLongest = 1;
        while (hashSet.count(++curNum)) {
          ++nowLongest;
        }
        res = max(res, nowLongest);
      }
    }
    return res;
  }
};

2025-02-02 该篇文章被 HopoZ 打上标签: leetcode hash 归为分类: algo