1+ /*
2+ Author: Andy, nkuwjg@gmail.com
3+ Date: Jun 18, 2014
4+ Problem: Longest Consecutive Sequence
5+ Difficulty: Hard
6+ Source: https://oj.leetcode.com/problems/longest-consecutive-sequence/
7+ Notes:
8+ Given an unsorted array of integers, find the length of the longest consecutive
9+ elements sequence.
10+ For example,
11+ Given [100, 4, 200, 1, 3, 2],
12+ The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
13+ Your algorithm should run in O(n) complexity.
14+
15+ Solution 1: Update solution.
16+ */
17+
18+ public class Solution {
19+ public int longestConsecutive (int []num ) {
20+ int size =num .length ;
21+ HashMap <Integer ,Integer >unmap =new HashMap <Integer ,Integer >();
22+ int res =0 ;
23+ for (int i =0 ;i <size ; ++i ) {
24+ if (unmap .containsKey (num [i ]) ==true )continue ;
25+ int val =num [i ];
26+ if (unmap .containsKey (val -1 ) ==true &&unmap .containsKey (val +1 ) ==true ) {
27+ unmap .put (val ,unmap .get (val -1 ) +unmap .get (val +1 ) +1 );
28+ unmap .put (val -unmap .get (val -1 ),unmap .get (val ));
29+ unmap .put (val +unmap .get (val +1 ),unmap .get (val ));
30+ }else if (unmap .containsKey (val -1 ) ==true ) {
31+ unmap .put (val ,unmap .get (val -1 ) +1 );
32+ unmap .put (val -unmap .get (val -1 ),unmap .get (val ));
33+ }else if (unmap .containsKey (val +1 ) ==true ) {
34+ unmap .put (val ,unmap .get (val +1 ) +1 );
35+ unmap .put (val +unmap .get (val +1 ),unmap .get (val ));
36+ }else {
37+ unmap .put (val ,1 );
38+ }
39+ res =Math .max (res ,unmap .get (val ));
40+ }
41+ return res ;
42+ }
43+ }
