题目描述（困难难度）

给一个数组，求出连续的数字最多有多少个，时间复杂度要求是 。

解法一

首先想一下最直接的暴力破解。我们可以用一个 HashSet 把给的数组保存起来。然后再考虑数组的每个数，比如这个数是 n，然后看 n + 1 在不在 HashSet 中，然后再看 n + 2 在不在，接下来 n + 3、n + 4 直到在 HashSet 中找不到，记录当前的长度。然后继续考虑下一个数，并且更新最长的长度。

当然时间复杂度不符合题意了，我们想一下优化方案。

上边的暴力破解有一个问题就是做了很多没必要的计算，因为我们要找最长的连续数字。所以如果是数组 54367，当我们遇到 的时候计算一遍 567。遇到 4 又计算一遍 4567。遇到 3 又计算一遍 34567。很明显从 3 开始才是我们想要的序列。

这个时间复杂度的话就是 了。虽然 for 循环里套了 while 循环，但每个元素其实最多也就是被访问两次。比如极端情况 987654 ，98765 循环的时候都不会进入 while 循环，只有到 4 的时候才进入了 while 循环。所以总共的话， 98765 也只会被访问两次，所以时间复杂度就是 O(n) 了。

解法二

参考 这里-solution-Accepted>) ，虽然不容易直接想到，但还是有迹可循的。

本质上就是把连续的序列进行合并，思路就是考虑我们先解决了小问题，然后大问题怎么解决。

实现的话，我们可以用一个 ，存储以当前 key 为边界的连续序列的长度。可以再结合代码理解一下。

总

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 查看详情