Longest Consecutive Sequence

解题思路

  1. 先思考最粗暴的解法，最直观的就是排序后遍历可得。

  2. 但是要求时间复杂度为 O(n)，则考虑增加空间复杂度来求解。

  3. 我的解法是通过 map 一次遍历可得，Solution 给出的解法是通过 set，理论上我的解法是要快一点的。

代码

// use unordered_map
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> hash;
        int max_count = 0;
        for (auto num : nums) {
            if (hash[num] != 0) {
                continue;
            }
            hash[num] = 1;
            int left_count = hash[num - 1];
            int right_count = hash[num + 1];
            int new_count = left_count + 1 + right_count;
            hash[num - left_count] = new_count;
            hash[num + right_count] = new_count;
            max_count = max(max_count, new_count);
        }
        return max_count;
    }
};


// use unordered_set
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> hash(nums.begin(), nums.end());
        int max_count = 0;
        for (auto num : nums) {
            int count = 1;
            if (hash.count(num - 1)) {
                continue;
            }
            while (hash.count(++num)) {
                ++count;
            }
            max_count = max(max_count, count);
        }
        return max_count;
    }
};