> For the complete documentation index, see [llms.txt](https://imhuay.gitbook.io/studies/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/niu-ke-0095-kun-nan-shu-zu-zhong-de-zui-chang-lian-xu-zi-xu-lie.md).
# 数组中的最长连续子序列
 [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#困难) [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#牛客) [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#滑动窗口) [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#哈希表hash) [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#并查集)
> [数组中的最长连续子序列\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/eac1c953170243338f941959146ac4bf)
**问题简述**
```
给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）
```
**思路1：排序+滑动窗口**
* 先排序（`O(NlngN)`）；
* 然后使用滑动窗口模板；
* **易错点**：考虑 `[0,1,1,2,3]`，答案应该是 4 而不是 3；
* 所以还要使用一个变量来记录区间内的重复值；
Python
```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：哈希表**
> [【动态规划】最长连续序列 - 江不知](https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/dong-tai-gui-hua-python-ti-jie-by-jalan/)
>
> > 不算是标准的动态规划，因为它不满足无后效性；
* 哈希表中的 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
```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
```
**其他思路**
> [哈希集合/哈希表/动态规划/并查集四种方法 - 超小白](https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/xiao-bai-lang-ha-xi-ji-he-ha-xi-biao-don-j5a2/)