LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 排序去重后动态规划，时间复杂度 O(n log n)

class Solution {
 public:
  int longestConsecutive(vector<int>& nums) {
    if (nums.empty()) {
      return 0;
    }
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    int res = 1;
    vector<int> dp(nums.size(), 1);
    for (int i = 1; i < nums.size(); ++i) {
      if (nums[i] == nums[i - 1] + 1) {
        dp[i] = dp[i - 1] + 1;
      }
      res = max(res, dp[i]);
    }
    return res;
  }
};

• 使用哈希表，时间复杂度O(n)

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