[LeetCode Hot 100] LeetCode128. 最长连续序列

题目描述

思路

将数组所有点映射到一个数轴上，可以发现问题变为求每段区间首元素到尾元素的长度的最大值。
区间的长度：区间尾元素值-区间首元素值 + 1

方法一：超出时间限制

这个方法是最初自己想到的，但是超时了，主要原因是程序会有冗余的遍历过程，增加了开销。
思路：(时间复杂度太高)

1. 先把所有元素加入到哈希表中
2. 遍历每一个元素n，看是否存在n+1，更新res
3. 求最大res

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
		// 定义一个哈希表
        Set<Integer> set = new HashSet<>();
		// ：将所有数添加到哈希表中
        for (int i : nums) set.add(i);
        int res = 0;
        
        for (int i = 0; i < nums.length; i ++) {
            int n = nums[i] + 1;
            while (set.contains(n)) {
                len = len + 1;
                n = n + 1;
            }
            res = Math.max(res, len);
        }
        return res;
    }
}

方法二：哈希表

求每段区间首元素到尾元素的长度的最大值

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        Set<Integer> set = new HashSet<>();
        for (int i : nums) set.add(i);
        int res = 0;
        
        for (int num : nums) {
            if(!set.contains(num - 1)) {
				// 说明是区间的首元素
                int x = num;
                while(set.contains(x + 1)) {
                    x ++;
                }
                res = Math.max(res, x - num + 1);
            }
        }
        return res;
    }
}