Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

128. 最长连续序列 #35

Open
webVueBlog opened this issue Sep 12, 2022 · 0 comments
Open

128. 最长连续序列 #35

webVueBlog opened this issue Sep 12, 2022 · 0 comments

Comments

@webVueBlog
Copy link
Owner

128. 最长连续序列

Description

Difficulty: 中等

Related Topics: 并查集, 数组, 哈希表

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

提示:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
// 1.将数组元素存入set中
// 2.遍历nums,如果当前项-1存在于set,说明当前项不是连续序列的起点,忽略,继续遍历
// 3.如果当前项没有“左邻居”,它就是连续序列的起点,循环查看当前项连续的右邻居有多少个
// 4.返回最长的连续次数
var longestConsecutive = function (nums) {
    // 把数组的数字全部放入set中,一来去重,二来方便快速查找
    const set = new Set(nums)
    let max = 0
    for (let val of nums) {
        // 没有左邻居,是序列的起点,才开始数数
        if (!set.has(val - 1)) {
            let count = 1
            let now = val
            // 有右邻居,看连续的右邻居右多少个
            while (set.has(now + 1)) {
                now++
                count++
            }
            // 存放最大的连续邻居的值
            max = Math.max(max, count)
        }
    }
    return max
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant