leetCode-128:Longest Consecutive Sequence

问题描述

给定一个整数数组，要求在 O(n) 的时间复杂度内找出数组中最长连续序列的元素个数。题目链接：**点我**

样例输入输出

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

输出：4

说明：最长连续序列为 1 2 3 4，序列中元素个数为 4

输入：[1, 2, 3, 4, 6, 7, 8, 9, 10]

输出：5

说明：最长连续序列为 6 7 8 9 10，序列中元素个数为 5

问题解法

遍历数组，将数组中每个元素放在 map 中，然后重新遍历数组中每个元素，以该元素为起点，每次加一，看新的数字是否在 map 中，如果在，则说明新的数字存在数组，同时也说明这个新的数字与当前元素是能构成连续序列的，如果不在，则说明新的数字不在数组中，结束循环。同样，以该元素为终点，每次减一，重复上述步骤，直到条件不满足为止。这样就能找出包含当前元素的最长序列的起始和终止的数字，进而获取到包含当前元素的最长序列的元素个数。在循环遍历数组时，每次比较最长序列的元素个数，取其最大值，当数组遍历完成时，变量保存的最大值就是求解的值。代码如下

class Solution
{
    public int longestConsecutive(int[] nums)
    {
        Map<Integer, Boolean> map = new HashMap<>(nums.length);
        for (int num : nums)
        {
            map.put(num, false);
        }

        int maxCount = 0;
        for (int num : nums)
        {
            int count = 0;
            if (!map.get(num))
            {
                count++;
                int next = num + 1;
                while (!map.getOrDefault(next, true))
                {
                    map.put(next, true);
                    count++;
                    next = next + 1;
                }

                int front = num - 1;
                while (!map.getOrDefault(front, true))
                {
                    map.put(front, true);
                    count++;
                    front = front - 1;
                }

                if (count > maxCount)
                {
                    maxCount = count;
                }
            }
        }

        return maxCount;
    }
}