数组中最长连续序列

一、题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

Leetcode：https://leetcode.cn/problems/WhsWhI/

Leetcode：https://leetcode.cn/problems/longest-consecutive-sequence/

二、分析

我们借助一个哈希表来做，map 的 key 存储的是数组中的元素，map 的 value 存储的是当前的 key 向左扩、或者向右扩最远能到达什么地方。

遍历数组的过程，拿到当前遍历到的数字，在 map 中寻找，如果能找到，说明是重复的元素，不用管。如果找不到，先把这个元素插入到 map 中，map[vec[i]] = 1。然后紧接着，判断 vec[i]-1 和 vec[i]+1 是否在 map 中。如果存在，说明当前元素可以向左扩、或者向右扩。

向左扩和向右扩完成之后，我们更新最左边、最右边的元素在 map 中的 value 值。

如下，看代码

class Solution {
public:
    int get_longest_consecutive(const std::vector<int>& arr) {
        if (arr.empty()) {
            return 0;
        }
        // 注意，这里必须为 1，因为数组中如果有值，那么必然最小的子序列长度为 1
        int res = 1;
        std::unordered_map<int, int> mp;
        for (int i = 0; i < arr.size(); ++i) {
            if (mp.find(arr[i]) == mp.end()) {
                mp[arr[i]] = 1;
                if (mp.find(arr[i]-1) != mp.end()) {
                    res = std::max(res, merge(mp, arr[i]-1, arr[i]));
                }
                if (mp.find(arr[i]+1) != mp.end()) {
                    res = std::max(res, merge(mp, arr[i], arr[i]+1));
                }
            }
        }
        return res;
    }

private:
    int merge(std::unordered_map<int, int>& mp, int less, int more) {
        int left = less - mp.at(less) + 1;
        int right = more + mp.at(more) - 1;
        int len = right - left + 1;
        mp[left] = len;
        mp[right] = len;
        return len;
    }
};

int main() {
    std::vector<int> arr{100, 4, 200, 1, 3, 2};
    Solution s;
    int res = s.get_longest_consecutive(arr);
    std::cout << res << std::endl;
    return 0;
}