By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、最长连续序列

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

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

示例:

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

1.1、解题思路

先全部放到set集合中去，然后依次遍历数组，如果发现num-1不在set集合中，则一直知道num+1，看看它是否也在集合中

1.2、算法

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet();
    for (int num : nums) {
        set.add(num);
    }

    int maxLen = 0;

    for (int num : set) {
        if (!set.contains(num - 1)) {
            int curLen = 1;

            while (set.contains(num + 1)) {
                curLen += 1;
                num += 1;
            }
            maxLen = Math.max(maxLen, curLen);
        }
    }
    return maxLen;
}

1.3、测试

 @Test
    public void test(){
        int[] nums = {100,4,200,3,2};
        System.out.println(longestConsecutive(nums));
    }

​

ContactAuthor