思路

由于需要我们查找连续数字,因此,我们需要对给定的数组进行排序,这样我们判断两个数字连续只需要判断$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)$,因为每个点都只会被所有循环加起来枚举到一次.

类似题目推荐

华为题库已更新至:华为实习&秋招真题题库，请移步。