Java for LeetCode 128 Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

解题思路:

由于是O(n)的时间复杂度,因此不能用排序实现,本题有点类似于第一题Java for LeetCode 001 Two Sum也需要用HashMap来实现,具体思路是先把nums装进Map中,然后对nums的每一个元素,检查其“势力范围"(本题不涉及重复元素),JAVA实现如下:

	public int longestConsecutive(int[] nums) {
		HashMap<Integer, Boolean> hm = new HashMap<Integer, Boolean>();
		int res = 0;
		for (int num : nums)
			hm.put(num, false);
		for (int num : nums) {
			if (hm.get(num))
				continue;
			int width = 1;
			for (int j = 1; hm.containsKey(num - j); j++, width++)
				hm.put(num - j, true);
			for (int j = 1; hm.containsKey(num + j); j++, width++)
				hm.put(num + j, true);
			res = Math.max(res, width);
		}
		return res;
	}
原文地址:https://www.cnblogs.com/tonyluis/p/4541003.html