p128

发表于 | 分类于 |

LeetCode 128 Longest Consecutive Sequence 题解

1.题目：

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.
Subscribe to see which companies asked this question

题意：

给一个乱序的数组，找出这个数组里连续的最长长度。

2.解题思路:

先用一个HashSet除去重复的值，再用一个HashSet从某点开始延展开来，记录两个端点，两个端点相减即为连续的长度，记录最大值。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 

public class Solution {
    public int longestConsecutive(int[] nums) {
       int ans = 0;
		HashSet<Integer> set = new HashSet<Integer>();
		HashSet<Integer> line = new HashSet<Integer>();
		for (int i = 0; i < nums.length; i++) {
			set.add(nums[i]);
		}
		int a = 0, b = 0;
		for (int i : set) {
			if (!line.contains(i)) {
				a = i + 1;
				while (set.contains(a)) {
					line.add(a);
					a++;
				}
				// System.out.println("aa "+a);
				b = i - 1;
				while (set.contains(b)) {
					line.add(b);
					b--;
				}
				// System.out.println("bb "+b);
				if (ans < (a - b - 1)) {
					ans = a - b - 1;
				}
				// System.out.println(ans);
			}
		}

		return ans;
    }
}

4.一些总结：