「笔试刷题」：数组中的最长连续子序列

一、题目

描述

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

数据范围：1≤n≤10^5，数组中的值满足 1≤val≤10^8

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

示例1

输入：

[100,4,200,1,3,2]

返回值：

4

示例2

输入：

[1,1,1]

返回值：

1

备注：

1≤n≤10^5
1≤arri​≤10^8

二、思路解析

一道朴素的模拟题，单纯的暴力解法肯定是会超时的，但我们可以做一点小优化。

而我做的优化，是通过 排序 + 双指针 实现的。

首先将数组排序，这样相邻的数值就会挨在一起。

然后就去遍历排序后的数组，通过一个变量 count 计算连续的序列长度，并用 ret 记录最长的长度。

在这个过程中，碰到大小相同的元素，直接让 j++ 就好，而 count 则不用计数。

最后返回最长的长度作为结果即可。

这道题十分考验我们的代码实现能力，i 和 j 两个数的赋值需要特别注意，稍一不小心就赋错值了。

好啦，具体实现请看下面代码