LeetCode 128. 最长连续序列

[yinxin630]

题目

https://leetcode-cn.com/problems/longest-consecutive-sequence/

思路

1. 使用 hash 表, map[n] 表示以数字 n 为端点的序列长度
2. map[n] = 1 + map[n - 1] + map[n + 1]. map[n - 1] 是前一个序列, map[n + 1] 是后一个序列, 前序列和后序列均可为空(长度 = 0)
3. 如果 map[n - 1] 不为空, 则更新 map[n - map[n - 1]] = map[n], 即前序列的左端点
4. 如果 map[n + 1] 不为空, 则更新 map[n + map[n + 1]] = map[n], 即后序列的右端点

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    const map = {};
    let max = 0;
    for (let i = 0; i < nums.length; i++) {
        if (map[nums[i]]) {
            continue;
        }

        map[nums[i]] = 1 + (map[nums[i] - 1] || 0) + (map[nums[i] + 1] || 0);

        if (map[nums[i] - 1]) {
            map[nums[i] - map[nums[i] - 1]] = map[nums[i]]
        }

        if (map[nums[i] + 1]) {
            map[nums[i] + map[nums[i] + 1]] = map[nums[i]]
        }

        max = Math.max(max, map[nums[i]]);
    }

    return max;
};