LeetCode HOT100 - 最长连续序列

因为时间复杂度是 O(n) ，所以不能排序后做

相当于只能遍历数组

那么想遍历的时候我们能做什么

那不就是相当于枚举当前元素作为起点的话连续序列的长度是多少吗

如果每个都这样去判断，那么首先，我们需要一个哈希表去 O(1) 的查询这个元素是否在数组中，接着，复杂度是类似于 \(O(n^2)\) 的

因此考虑怎么优化

可以想到，比如 1 2 3 4 ，我们已经看过 1 作为起点了，那么 2，3，4 实际上都没有必要看了，因此我们的哈希表可以变成一个 vis 数组的形式，判断这个元素有没有被处理过，处理过我们就没必要看了

接着仍然是 1 2 3 4，考虑我们 2 为起点的已经遍历过了，那么现在再从 1 开始是不是可以使用一些 2 的信息，可以继续在哈希表上维护，例如 mp[2] 表示以 2 为起点的答案，这样从 1 开始到 2 的时候就可以结束遍历直接借用 2 的答案了

因为一定是从前往后的，所以只在起点处更新它那个位置的答案不会有问题

class Solution {
public:
    int longestConsecutive(vector<int>& a) {
        unordered_map<int, int> mp;
        int n = a.size();
        for (int i = 0; i < n; i++) {
            mp[a[i]] = -1;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (mp[a[i]] == -1) {
                int cur = 1;
                while (mp[a[i] + cur] == -1) {
                    mp[a[i] + cur] = 1;
                    cur++;
                }
                mp[a[i]] = mp[a[i] + cur] + cur;
                ans = max(ans, mp[a[i]]);
            }
        }
        return ans;
    }
};

实际上感觉和正解的思路差不多

不过正解有一个点就是如果 x−1 在哈希集合中，则不以 x 为起点。为什么？因为以 x−1 为起点计算出的序列长度（https://leetcode.cn/problems/longest-consecutive-sequence/solutions/3005726/ha-xi-biao-on-zuo-fa-pythonjavacgojsrust-whop）
这样可以略去一些情况，算是一种剪枝的优化