每天一道算法题（三）——获取数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

---

前言

提示：想要理解方法2，希望你了解set对象后进行查看。

---

1、问题

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

2、示例

示例 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

3、解决方法

（1）方法1——排序

let nums = [100,4,101,1,3,2]
/**
 * @param {number[]} nums    一个未排序的数组
 * @return {number}   返回一个数字连续的最长序列的长度
 */
// 方法一  排序 
let longestConsecutive = function(nums) {
    let list = nums.sort((a,b)=> a-b); // 1:排序（从小到大）
    console.log('排序后的数据', nums); // [1, 2,3,4,100,101]
    let max = 0; // 2-1:设置返回的最大值
    let count = 1; // 2-2:设置存储连续值
    for(let i =0;i<nums.length-1; i++){
        let cur = i, next = i+1; // 3：定义对比的第一个值，对比的第二个值
        if(list[cur] == list[next]) continue  // 4:如果第一个值和第二个值相同就跳过此次循环
        // 5-1:如果第一项加1 等于  第二项  说明连续，就自增连续值 count++，
        if(list[cur] + 1 === list[next]){
            count ++ 
        } else {
            // 5-2:如果不等于就把这个值设置为初始值
            count = 1
        }
        // 6:获取 max和count 的最大值并赋值给max
        max = Math.max(max, count)
    }
    // 7：返回最大的连续数组
    console.log('最终数据', max); // 最终数据 4
    return max;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

（2）方法2——set

关键方法：set.has(值) 如果set数据中有has中的值，就返回true，否则返回false

let nums = [100,4,101,1,3,2]

let longestConsecutive = function(nums){
    const set = new Set(nums); // 1：将数组的所有数据放到set中
    let max = 0; // 2:设置最大连续值
    for (let i=0;i<nums.length; i++){
        // 3: 判断是不是第一项（第一项左侧没有值的话就是第一项）
        if(!set.has(nums[i]-1)){
            let start = nums[i] // 3-1: 如果是第一项就记录下为第一项的值
            let count = 1;  // 3-2: 设置存储连续值
            // 3-3 循环第一项的右边那项，当右边没有值的时候停止
            while(set.has(start + 1) ){
                start++;
                count++;
            }
            max = Math.max(max, count)
        }
    }
    console.log('最终数据', max); // 最终数据 
}
longestConsecutive(nums)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21