算法11.數(shù)組的最長(zhǎng)連續(xù)序列

題目：

? ? 給定一個(gè)未排序的整數(shù)數(shù)組，找出最長(zhǎng)連續(xù)序列的長(zhǎng)度。

? ? 要求算法的時(shí)間復(fù)雜度為 O(n)。

示例：

? ? 輸入: [100, 4, 200, 1, 3, 2]

? ? 輸出: 4

? ? 解釋: 最長(zhǎng)連續(xù)序列是 [1, 2, 3, 4]。它的長(zhǎng)度為 4。

解題思路：

????當(dāng)前數(shù)字的最大連續(xù)序列長(zhǎng)度一定是它前一個(gè)數(shù)字的長(zhǎng)度+?后一個(gè)數(shù)的長(zhǎng)度，再加上1。然后我們使用一個(gè)hash表來記錄每個(gè)數(shù)字遍歷過程中的最大序列長(zhǎng)度。

代碼如下：

/** * @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);    }    /**     * 最長(zhǎng)連續(xù)序列     * @param nums     * @return     */    private static int longestSequence(int[] nums){        int maxLen = 0;        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0;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;    }}