数组中的最长连续子序列

数组中的最长连续子序列_牛客题霸_牛客网

问题简述

给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）

思路1：排序+滑动窗口

• 先排序（O(NlngN)）；

• 然后使用滑动窗口模板；

• 易错点：考虑 [0,1,1,2,3]，答案应该是 4 而不是 3；

  • 所以还要使用一个变量来记录区间内的重复值；

Python

class Solution:
    def MLS(self , arr: List[int]) -> int:
        N = len(arr)
        arr.sort()
        
        def check(l, r, rep):  # O(1) 判断是否连续
            return l < r and arr[r] - arr[l] != r - l - rep
        
        l, r = 0, 0  # 闭区间窗口
        rep = 0  # 记录区间内的重复次数
        ret = 0
        while r < N:
            while check(l, r, rep):  # 当不满足时，右移 l
                if l + 1 < N and arr[l] == arr[l + 1]:
                    rep -= 1
                l += 1
                
            ret = max(ret, r - l + 1 - rep)
            if r + 1 < N and arr[r] == arr[r + 1]:
                rep += 1
            r += 1
            
        return ret

思路2：哈希表

【动态规划】最长连续序列 - 江不知

不算是标准的动态规划，因为它不满足无后效性；

• 哈希表中的 key 和 value 分别表示什么？

  • 区间长度 value 和它的两个端点 [key1, key2]；

  • 如果 value = 1，则 key1 == key2；

• 算法流程：

  1. 初始化哈希表 book；

  2. 遍历 arr 中每个 x；

  3. 若 x 不在 book 中，执行：

     1. 初始化 book[x] = 1 表示区间 [x, x] 的长度为 1（也可以理解为 x 出现过的标记）；

     2. 查询 l = book[x-1] 和 r = book[x+1]，分别表示 x 左右区间的长度，若不存在则为 0；则 [x-l, x+r] 这段区间内的长度为 l + 1 + r；

     3. 根据 book 的定义，因为 x 把左右区间连通了，所以需要更新 book[x-l] 和 book[x+r]

• 为什么 book[x-1] 和 book[x+1] 代表的区间一定在 x 两侧？换言之，为什么这两个区间是 [x-l, x-1] 和 [x+1, x+r]，而不是 [x-1, x+l] 和 [x-r, x+1]？；

  • 因为执行上述操作的前提是 x 没有出现过；如果 x 出现过，就和 book 的定义发生了冲突，即违反了 book[x - l] = book[x + r] = l + 1 + r 这一步操作；

Python

class Solution:
    def MLS(self , arr: List[int]) -> int:
        
        book = dict()
        ret = 0
        for x in arr:
            if x not in book:
                book[x] = 1
                l, r = book.get(x - 1, 0), book.get(x + 1, 0)
                mx = book[x - l] = book[x + r] = l + 1 + r
                ret = max(ret, mx)
        
        return ret

其他思路

哈希集合/哈希表/动态规划/并查集四种方法 - 超小白