思路

由于需要我们查找连续数字,因此,我们需要对给定的数组进行排序,这样我们判断两个数字连续只需要判断 $arr[i]-arr[i-1]==1$ 即可.

那么我们可以对于每一个数字 $arr[i]$ 都以它本身编号i为起始编号,不断向后查找求得最长长度,时间复杂度为 $O(n^2)$ .这个时间复杂度可以优化.我们发现假设i为起始编号对应最长长度为 $cnt(cnt>1)$ ,那么 $i+1$ 为起始编号时,最长长度肯定是 $cnt-1$ .因此,我们一旦发现最长长度 $cnt$ 大于1时,那么后续的 $cnt-1$ 个数都不需要寻找最长长度,因为必定小于 $cnt$ .

按照上面的思路,我们假设 $i$ 为起始编号时,对应最长长度为 $cnt$ .此时,下一步我们需要判断的下标就可以为 $i+cnt$ ,其中 $[i+1,i+cnt-1]$ 的下标都不需要判断最长长度.所以总的时间复杂度为 $O(n)$ ,因为每个点都只会被所有循环加起来枚举到一次.