题解 | #数组中的最长连续子序列#

解题思路

为求数组中的最长连续子序列，可能会想到利用排序，先对数组排序，再遍历枚举找到最长连续子序列，但排序时间复杂度至少都是nlg(n)
下面介绍一种不需要排序的时间复杂度O（n）算法，我们从做到右遍历数组，对于每一个元素，枚举它的最长连续子序列，在枚举的过程中，我们要判断元素是否在数组中，因此我们引入哈希表，把查找元素的时间复杂度降到O(1),比如遍历到数组的元素x,我们枚举x + 1, x + 2, x + 3....是否在数组中，寻找最长连续子序列

优化

上面的思路存在很多的重复枚举，我们观察连续子序列，x, x + 1, x + 2, x + 3, x + 4....,枚举x + 1是没必要的，因为从x出发会重新枚举一遍，而且长度更长，所以我们只需要枚举连续子序列的最小元素即可。在代码实现时，当我们遍历到元素x时，判断x - 1是否在数组中，在，则跳过枚举，不在，则枚举。

• 时间复杂度：，遍历数组的时间
• 空间复杂度：, 哈希表存放元素的开销空间

代码

import java.util.*;
public class Solution {
    public int MLS (int[] arr) {
        Set<Integer> set = new HashSet<>();
        int max_len = 0;
        for (int c : arr){
            set.add(c);
        }
        for (int i = 0; i < arr.length; i++){
            if (set.contains(arr[i] - 1)){
                continue;
            } else {
                int j = 1;
                while (true){
                    if (set.contains(arr[i] + j)) j++;
                    else break;
                }
                max_len = Math.max(max_len, j);
            }
        }
        return max_len;
    }
}