算法11.数组的最长连续序列

题目：

    给定一个未排序的整数数组，找出最长连续序列的长度。

    要求算法的时间复杂度为 O(n)。

示例：

    输入: [100, 4, 200, 1, 3, 2]

    输出: 4

    解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

解题思路：

    当前数字的最大连续序列长度一定是它前一个数字的长度+?后一个数的长度，再加上1。然后我们使用一个hash表来记录每个数字遍历过程中的最大序列长度。

代码如下：

/** * @author Ted * @version 1.0 * @date 2021/10/26 11:03 */public class MaxLengthSequence {
    public static void main(String[] args) {        int[] nums = new int[]{100,4,200,1,3,2,5};        int i = longestSequence(nums);        System.out.println(i);    }    /**     * 最长连续序列     * @param nums     * @return     */    private static int longestSequence(int[] nums){        int maxLen = 0;        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++) {
            if(map.get(nums[i])==null) {                map.put(nums[i],1);                int left = 0,right = 0;                if(map.containsKey(nums[i]-1)) {                    left = map.get(nums[i]-1);                }                if(map.containsKey(nums[i]+1)) {                    right = map.get(nums[i]+1);                }
                int curLen = left+right+1;                maxLen = Math.max(maxLen, curLen);                map.put(nums[i],maxLen);
                //直接算出需要更新的两端位置                if(map.containsKey(nums[i]-left)){                    map.put(nums[i]-left, curLen);                }                if (map.containsKey(nums[i]+right)){                    map.put(nums[i]+right,curLen);                }            }        }        return maxLen;    }}