128. [✔][M]最长连续序列

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

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

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

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

---

题解：

// @lc code=start
function longestConsecutive(nums: number[]): number {
    let map = new Set<number>();
    for (let i = 0; i < nums.length; i++) {
        map.add(nums[i]);
    }

    let res = 0;

    for (const num of map) {
        if (map.has(num)) {
            continue;
        }

        let current = num;
        let currentSize = 1;

        while (map.has(current + 1)) {
            current += 1;
            currentSize += 1;
        }

        res = Math.max(res, currentSize);
    }

    return res;
};


// 第二种解法
function longestConsecutive(nums: number[]): number {
    let map = new Map();
    let res = 0;

    for(let num of nums){
        if(map.has(num)) continue;
        let leftNumberLongestLength = map.get(num-1) || 0;//左边那个数字保存的最长序列数量
        let rightNumberLongestLength = map.get(num+1) || 0;//右边那个数字保存的最长序列数量

        //为什么直接加起来就可以？
        // 因为 当前数字num在左侧数字num-1的右边，左侧数字num-1保存的leftNumberLongestLength一定是从左边某个位置一直到左边数字num-1的连续序列长度
        // 同理右侧数字num+1保存的rightNumberLongestLength是num+1到最右边某个位置的连续长度
        // 再加上自己，就是从最左边到最右边的连续长度
        let selfNumberLongestLength = leftNumberLongestLength +rightNumberLongestLength + 1;

        res = Math.max(res,selfNumberLongestLength);

        // 寻找num值连续序列最左边的值和最右边的值
        let leftestNumberValue = num - leftNumberLongestLength;
        let rightestNumberValue = num + rightNumberLongestLength;

        //更新两头数字上保存最长值
        map.set(num,selfNumberLongestLength);
        map.set(leftestNumberValue,selfNumberLongestLength);
        map.set(rightestNumberValue,selfNumberLongestLength);

    }

    return res;
};
// @lc code=end