hello，兄弟们，我又来了。现在秋招在即，身边牛逼的大佬已经开始在准备着秋招了，但是我还有好多东西没有学啊，得加班加点的多学点东西了。所以还是多刷点算法，努力的打好自己的基础！嗯，就是这样的。不说了，还是写点算法吧

手刃算法第六式：最长连续序列

给定一个未排序的整数数组 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

我的解答

我看到这个题，我第一想法就是将这个数组进行排序，然后循环这个数组判断它是否连续。但是，我没有想到如何判断一个数是否连续，最后chat了一下，才发现居然可以利用两个连续的相邻的数之差为1。天哪，这个想法实在是太妙了（对我来说，我相信对广大掘友来说就是洒洒水啦）。看了一下这个思想，我瞬间想把自己的脑子丢掉了！这么简单的思想都没想到。好啦，既然已经有了一定的想法，那就手动去用代码实现吧！

具体的代码实现如下：

var longestConsecutive = function(nums) { 
    const newNums = nums.sort((a,b)=>a-b) 
    let len = newNums.length 
    let count = 1 
    let maxCount=1 
    if(len == 0){
        return 0
    }
    for(let i = 1 ;i<len;i++){ 
        if(newNums[i]-newNums[i-1] == 1){ 
           count++
           maxCount = Math.max(count,maxCount)
        }
        else if(newNums[i]-newNums[i-1] == 0){
            continue
        }else{      
            count = 1
        }  
    }
    return maxCount
}

这段代码还是经过千辛万苦才敲出来的（别喷我），一方面是自己对这个算法还是不够熟悉，另一方面室友在边上打游戏巨大的声音，写不了一点。经过不断地测试，程序终于不报错了，才得出这段代码。这段代码思想较为简单，就是将数组进行重新排序，设置一个计数器count，再设计一个最大长度标记maxCount，循环数组判断相邻的两个数是否连续。每进行一次循环就与将count与maxCount对比一次。

其实这样还是有点重复比较了，性能不是很好的样子。但是这还是我经历了许多次失败的，其中主要的问题有着三个：

• 我将这个比较放在最后面那个else里面，导致一直进不到后面的else里面，就导致最后的结果一直为1。
• 我将比较放在第一个if判断里面，这样就很好解决了这个问题，但是给出的测试里面有一个输入的数组为空，这时候我还返回的是一个1，应该是要返回0的
• 最后就添加了一个if(len == 0){return 0}判断一下

这就是我在写这道题出现的一些问题，大家不要跟我一样哟。

最后再精简一下，可以得到个比较优美的代码：

var longestConsecutive = function(nums) {
    const newNums = nums.sort((a,b)=>a-b)
    if (nums.length === 0) return 0;
    let len = newNums.length
    let count = 1 
    let maxCount=1
    for(let i = 1 ;i<len;i++){
        if(newNums[i]-newNums[i-1] === 1){
            count++
            maxCount = Math.max(count,maxCount)
        }else if(newNums[i] !== newNums[i-1]){
          count = 1
        }
    }
    return maxCount
};

就不用我想的那么复杂了，就两种情况（其实也是三种），一种是相邻两者相减为1的，另外一种就是两个都不相等的。

官方解答

做完之后看了一下官方的解答，就是通过hash表来解这道题。

• 创建一个哈希表存储数组中的数

• 用哈希表查找这个数前面一个数是否存在，即num-1在序列中是否存在。存在那这个数肯定不是开头，直接跳过。

• 因此只需要对每个开头的数进行循环，直到这个序列不再连续。

以题解中的序列举例: [100，4，200，1，3，4，2] 去重后的哈希序列为： [100，4，200，1，3，2] 按照上面逻辑进行判断：

1. 元素100是开头,因为没有99，且以100开头的序列长度为1
2. 元素4不是开头，因为有3存在，过，
3. 元素200是开头，因为没有199，且以200开头的序列长度为1
4. 元素1是开头，因为没有0，且以1开头的序列长度为4，因为依次累加，2，3，4都存在。
5. 元素3不是开头，因为2存在，过，
6. 元素2不是开头，因为1存在，过。 完

具体代码实现如下：

function longestConsecutive(nums) {
    const numSet = new Set(nums);
    let longestLen = 0;

    for (const num of numSet) {
        if (!numSet.has(num - 1)) {
            let currentNum = num;
            let currentLen = 1;

            while (numSet.has(currentNum + 1)) {
                currentNum += 1;
                currentLen += 1;
            }

            longestLen = Math.max(longestLen, currentLen);
        }
    }

    return longestLen;
}

我个人觉得这个判断连续设计的非常巧妙！！！真的，我想不了一点。利用num-1判断是否作为连续的开头，然后利用num+1判断连续的长度。这个方法太强了，不过小菜鸡我理解起来还是有点困难，理清楚就好点了。这个性能也是不错的！我就不展示了，感兴趣的可以试一试。

学到了学到了！！

结束语

算法还是比较基础的，通过写算法还是反映出了我的不少问题，算法还得继续写，问题还得继续解决，晚安！