先排序
因为数组是无序的，如果要想找出最长的连续序列（这里序列的顺序可以打乱），我们最容易想到的就是先对数组进行排序，然后再查找。
使用一个变量count来记录当前有序序列的长度。
- 如果当前元素比前一个大1，说明他们可以构成连续的序列，count就加1。
- 如果相等就跳过。
- 否则就不能构成连续的序列，count要重置为1，要重新统计。
原理比较简单，我们来看下代码
public int MLS(int[] arr) {
if (arr == null || arr.length == 0)
return 0;
int longest = 1;//记录最长的有序序列
int count = 1;//目前有序序列的长度
//先对数组进行排序
Arrays.sort(arr);
for (int i = 1; i < arr.length; i++) {
//跳过重复的
if (arr[i] == arr[i - 1])
continue;
//比前一个大1，可以构成连续的序列，count++
if ((arr[i] - arr[i - 1]) == 1) {
count++;
} else {
//没有比前一个大1，不可能构成连续的，
//count重置为1
count = 1;
}
//记录最长的序列长度
longest = Math.max(longest, count);
}
return longest;
} 时间复杂度：O（nlog(n)），排序的复杂度是nlog(n)，for循环是n，相加是nlog(n)+n，所以时间复杂度是nlog(n)。
空间复杂度：O（1），就使用两个变量
看一下运行结果
使用集合Set解决
如果不排序的话，我们可以先把数组中的元素全部放到集合set中，然后再查找。假如有最长连续序列
x，x+1，x+2……x+n
我们只有从x往后查找才能找出最长的序列，因为从x+1往后查找的有序序列长度肯定是小于从x往后查找的有序序列长度的。
明白了这点，代码就容易写了，我们需要从有序序列的最小值开始计算即可，来看下代码
public int MLS(int[] arr) {
//先把数组放到集合set中
Set<Integer> set = new HashSet<>();
for (int num : arr)
set.add(num);
int longest = 0;//记录最长的有序序列
for (int num : arr) {
//这里要找有序序列最小的元素（不一定是最长
//有序序列的）。如果还有更小的，说明当前元素
//不是最小的，直接跳过
if (set.contains(num - 1))
continue;
//说明当前元素num是当前序列中最小的元素（这里
//的当前序列不一定是最长的有序序列）
int currentNum = num;
//统计当前序列的长度
int count = 1;
while (set.contains(currentNum + 1)) {
currentNum++;
count++;
}
//保存最长的值
longest = Math.max(longest, count);
}
return longest;
} 时间复杂度：O（n），for循环是n，只有遇到有序序列最小元素的时候才会执行while里面的循环。
空间复杂度：O（n），使用集合set存储数组中的所有元素
看下运行结果
截止到目前我在公众号“数据结构和算法”中已经写了500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
京公网安备 11010502036488号