LeetCode-128-最长连续序列

题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

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

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

题解

这一题一开始用双指针暴力解法，但是超时了，怎么也过不了。然后换了一个哈希表的解法，46%还凑活吧。

思路还是很简单的，就是我们用map保存连续的数字（相同的数字只保留一个），然后比较这些map的最大长度就可以了。

class Solution {
    public int longestConsecutive(int[] nums) {
        // List<Map<Integer, Integer>> 存放每个连续的数字段
        List<HashMap<Integer, Integer>> list = new ArrayList<>();
        // list中的第几个
        int index = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            HashMap<Integer, Integer> map = new HashMap<>();
            // 第一个数据特殊处理
            if (i == 0) {
                map.put(nums[i], index);
                list.add(map);
                continue;
            }
            // 从第二个开始，如果当前数字比上一个数字大1，说明是连续数字
            if (nums[i] - nums[i - 1] == 1) {
                if (list.get(index).get(nums[i]) == null) {
                    list.get(index).put(nums[i], index);
                }
            } else if (nums[i] != nums[i - 1]) { // 不连续而且不相同的时候，加入新的数据
                map.put(nums[i], index++);
                list.add(map);
            }
        }
        int res = 0;
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).size() > res) {
                res = list.get(i).size();
            }
        }
        return res;
    }
}