题目描述

// 128. 最长连续序列

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

// 进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？

题解

// 排序法
// 直接排序，res保存答案，count保存序列记录长度。
// for循环遍历nums的元素，记为nums[i]，如果相邻两个元素nums[i]和nums[i-1]
// 相等，直接跳过（相当于去重）。
// 如果相邻两个元素nums[i]-nums[i-1]=1，数值正好差1，说明是同一个序列，
// count数量+1。如果相邻元素既不是相等，数值也不是差1。说明肯定是数值差了很多
// ，两个元素已经不在一个序列，则将记录的count拿来更新res。count重新置1。
// 最后结束时再拿count更新一下res，返回res。

// 执行用时：4 ms, 在所有 Java 提交中击败了86.98%的用户
// 内存消耗：38.8 MB, 在所有 Java 提交中击败了40.24%的用户
class Solution {
    public int longestConsecutive(int[] nums) {
		if (nums.length == 0)
			return 0;
		Arrays.sort(nums);
		int res = 0;
		int count = 1;
		for (int i = 1; i < nums.length; i++) {
			if (nums[i] == nums[i - 1]) 
				continue;
			else if (nums[i] - nums[i - 1] == 1) 
				count++;
			else {
				res = Math.max(res, count);
				count = 1;
			}
		}
		res = Math.max(res, count);
		return res;
    }
}



// Hashset方法。
// 
// 思路是一样的，相当于拿hashset去重了，每次遍历元素num时，如果num++也存在
// 在set中，count计数一次，如此循环。最后更新res。
// 执行用时：1212 ms, 在所有 Java 提交中击败了5.00%的用户
// 内存消耗：40.5 MB, 在所有 Java 提交中击败了5.00%的用户
import java.util.HashSet;
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0)
            return 0;
		Set<Integer> set = new HashSet<>();
		int res = Integer.MIN_VALUE;
		for (int num: nums)
			set.add(num);
		for (int num: nums) {
			int count = 0;
			while (set.contains(num++)) {
				count++;
            }
			res = Math.max(res, count);
		}
		return res;
    }
}



// 优化一下，双O(n)的复杂度。
// 执行用时：373 ms, 在所有 Java 提交中击败了7.73%的用户
// 内存消耗：40 MB, 在所有 Java 提交中击败了10.25%的用户
import java.util.HashSet;
class Solution {
    public int longestConsecutive(int[] nums) {
		if (nums.length == 0)
            return 0;
		Set<Integer> set = new HashSet<>();
		int res = Integer.MIN_VALUE;
		for (int num: nums)
			set.add(num);
		for (int num: nums) {
			if (set.contains(num - 1))
				continue;
			else {
				int count = 0;
				while (set.contains(num++))
					count++;
				res = Math.max(res, count);
			}
		}
		return res;
    }
}