最长连续序列

最长连续序列 (opens new window)

题目要求的连续序列中的数字在原数组中可以是分散的，并且原数组中的数字可能是重复的。那么，要找到最长连续序列需要做的就是两步：

1. 原数组去重。
2. 记录去重后数组中，以每一个数字为序列起点的序列的长度。记录并找到最大的长度。

这道题其实在提示我们Set也可以作为哈希表使用。首先Set可以非常简单的实现数组的去重，这是第一个。其次我们在寻找连续序列时，如果当前遍历到的数是i，那么直接去Set中寻找是否存在i+1就可以知道连续序列是否还能进行下去。

var longestConsecutive = function(nums) {
    // 数组去重的同时，无意间也创建了一个哈希表
    const set = new Set(nums)
    let max = 0
    for (let i = 0; i < nums.length; i++) {
        // 存在比nums[i]刚好小1的数组，说明以nums[i]为起点的肯定不是最长连续序列，因为序列左边还有一个连续的数
        if (!set.has(nums[i] - 1)) {
            let cur = nums[i], count = 1
            while (set.has(cur + 1)) {
                cur++
                count++
            }
            max = Math.max(max, count)
        }
    }
    return max
};