题解 | 最长的连续元素序列长度

#include <algorithm>
#include <vector>
class Solution {
  public:
    /**
     *
     * @param num int整型vector
     * @return int整型
     */
    int longestConsecutive(vector<int>& num) { // 哈希表查找是o(1)
        // write code here
        unordered_set<int> res;
        for (int n : num) {
            res.insert(n);
        }
        int maxLength = 0;
        for (int n : num) {
            if (res.find(n - 1) == res.end()) {
                int currentNum = n;
                int currentLength = 1;
                while (res.find(currentNum + 1) != res.end()) {
                    currentNum++;
                    currentLength++;
                }
                maxLength = max(maxLength, currentLength);
            }
        }
        return maxLength;
    }
};

1. 哈希表存储元素：使用哈希表（在 C++ 中可以用 unordered_set ，在 Python 中可以用 set ）来存储数组中的所有元素。哈希表的特点是查找元素的时间复杂度接近 O(1) ，相比在数组中线性查找元素（时间复杂度 O(n) ）要快很多。例如，在判断一个数是否在数组中时，如果用数组线性查找，最坏情况要遍历整个数组；而用哈希表，能快速得到结果。
2. 确定连续序列起始点：遍历数组中的每个元素，对于某个元素 x ，先判断 x - 1 是否在哈希表中。如果 x - 1 不在哈希表中，这就表明 x 是某个连续序列的起始数字。因为如果 x - 1 存在，那么以 x 为起始的连续序列就可以和前面的数连接起来，x 就不是真正的起始点了。比如在数组 [1, 2, 3] 中，2 就不是起始点，因为 1 存在，连续序列从 1 开始。
3. 扩展连续序列并统计长度：当确定 x 是起始数字后，从 x 开始不断找下一个连续的数字，也就是判断 x + 1 、x + 2 等是否在哈希表中。每找到一个连续的数字，就更新当前连续序列的长度。例如，确定 1 是起始数字后，发现 2 也在哈希表中，此时连续序列长度从 1 变为 2 ，继续判断 3 ，如果 3 也在，长度就变为 3 ，依此类推。
4. 更新最长长度：在遍历数组并对每个起始数字扩展连续序列的过程中，记录下每次得到的连续序列长度，不断和当前已知的最长连续序列长度比较，取较大值更新最长长度。遍历完整个数组后，得到的最长长度就是题目要求的结果。