128. Longest Consecutive Sequence

Problem Description:

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

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Analysis:

本题使用HashSet来存放元素，然后对数组在进行两个方向上的扫描得出最后的结果。代码如下：

Code:

 

class Solution { public int longestConsecutive(int[] nums) { if(nums.length < 1) return 0; int maxLen = 1; Set<Integer> numSet = new HashSet<>(); for(int i = 0; i < nums.length; i++) { numSet.add(nums[i]); } for(int i = 0; i < nums.length; i++) { if(!numSet.contains(nums[i])) { continue; } numSet.remove(nums[i]); int prev = nums[i]; int nxt = nums[i]; while(numSet.contains(prev - 1)) { prev--; numSet.remove(prev); } while(numSet.contains(nxt + 1)) { nxt++; numSet.remove(nxt); } maxLen = Math.max(maxLen, nxt - prev + 1); } return maxLen; } }