128. Longest Consecutive Sequence

[Tcdian]

128. Longest Consecutive Sequence

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

Example

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. 
             Therefore its length is 4.

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    const cache = new Map();
    let result = 0;
    for (let i = 0; i < nums.length; i++) {
        // 已经出现过的元素，一定要跳过，防止更新后的边界变小。
        if (cache.has(nums[i])) {
            continue;
        }
        let leftBoundary = nums[i];
        let rightBoundary = nums[i];
        const leftElement = cache.get(nums[i] - 1);
        if (leftElement !== undefined) {
            leftBoundary = leftElement[0];
        }
        const rightElement = cache.get(nums[i] + 1);
        if (rightElement !== undefined) {
            rightBoundary = rightElement[1];
        }
        cache.set(nums[i], [leftBoundary, rightBoundary]);
        cache.set(leftBoundary, [leftBoundary, rightBoundary]);
        cache.set(rightBoundary, [leftBoundary, rightBoundary]);
        result = Math.max(rightBoundary - leftBoundary + 1, result);
    }
    return result;
};

• TypeScript Solution

function longestConsecutive(nums: number[]): number {
    const cache: Map<number, [number, number]> = new Map();
    let result = 0;
    for (let i = 0; i < nums.length; i++) {
        // 已经出现过的元素，一定要跳过，防止更新后的边界变小。
        if (cache.has(nums[i])) {
            continue;
        }
        let leftBoundary = nums[i];
        let rightBoundary = nums[i];
        const leftElement = cache.get(nums[i] - 1);
        if (leftElement !== undefined) {
            leftBoundary = leftElement[0];
        }
        const rightElement = cache.get(nums[i] + 1);
        if (rightElement !== undefined) {
            rightBoundary = rightElement[1];
        }
        cache.set(nums[i], [leftBoundary, rightBoundary]);
        cache.set(leftBoundary, [leftBoundary, rightBoundary]);
        cache.set(rightBoundary, [leftBoundary, rightBoundary]);
        result = Math.max(rightBoundary - leftBoundary + 1, result);
    }
    return result;
}