128.md

128. Longest Consecutive Sequence

Leetcode link

解题思路

本题要求我们找出一个给定数组的最长连续元素序列，并要求时间复杂度要是 O(n)

我们考虑到数组中的一个数 x，要求出它的最长连续元素序列，我们会需要一层 O(n) 循环来遍历数组

但是这个 O(n) 的过程也可以用一个哈希表来替代，这样查看一个数是否存在就可以简化成 O(1) 的复杂度

但是即使是这样我们的复杂度在最坏的情况也会达到 $$O(n^2)$$

所以需要对遍历的元素做一个筛减：

• 首先如果有一个数 x，那么如果它的 x - 1 存在集合中，我们不需要遍历
• 如果有一个数 x，如果它的 x + 1 存在集合中，我们需要把它的最长连续元素序列一个个找出来

第二点容易理解，我来说说为什么要有第一点：假定有个数组是 [x, x+1, x+2, x+3, x+4] 那么我们应该都会预期是从 x 开始逐个往 x + 4 来找对吧，如果没有第一条的话，我们对 x+1 ~ x+4 的寻找就是多余的了，所以不应该计算

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    let res = 0;
    let set = new Set();
    for(let num of nums) {
        set.add(num);
    }
    
    for(let num of nums) {
        // 只有在当前数字没有比它小一的数字在集合中时才进入
        if(!set.has(num - 1)) {
            let curNum = num;
            let curStreakLen = 1;
            
            while(set.has(curNum + 1)) {
                // 寻找集合中比它大一的数字
                curNum++;
                curStreakLen++;
            }
            
            res = Math.max(curStreakLen, res);
        }
    }
    return res;
};