Problem:

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.

Analysis:

This problem is good example of the great usage of HashMap in tackling String/Array problem. Up to now, we have encounter two kinds of problem could be magically simplified by using HashMap. 1. the substring meet certain qualifications (usually against another String): permutation, combination and substring. skill: usually use two hashmaps along with a count2. try to get the order inforamtion of elements of an array in linear time. Use a hashmap to record each element's appearnce. Then use map.(containsKey(target)) to check their appearance.Basic idea:1. use a hashmap to record each element's appearnce.HashMap
     
       map = new HashMap
      
        ();    for (int i = 0; i < nums.length; i++)        map.put(nums[i], 1);Note: don't wrongly write it into "map.put(i, 1)".2. then start  to scan the array from the beginning, for the current element cur, we check along the left side and then right side based on the cur's value. 3. once a sequence was recognized, we compare it's length with the global max, then update on the global max's value.for (int i = 0; i < nums.length; i++) {    int cur = nums[i];    int count = 1;    if (map.get(cur) != 0) {        //map.put(cur, 0);        while (map.containsKey(++cur)) {            map.put(cur, 0);            count++;        }        cur = nums[i];        while (map.containsKey(--cur)) {            map.put(cur, 0);            count++;        }    }    if (count > max)        max = count;}Skill:Once we visit a element, we reset it's value into "0". It means it's sequence has already been scanned. We do not need to scan it again. (This could save a lot of efforts)while (map.containsKey(++cur)) {    map.put(cur, 0);    count++;}Note: we are not set map.put(nums[i], 0) to save cost. Since all elements in the array is distinct, this element would not be reached again. Error:Use "while (map.containsKey(cur++))" to produce infinte loop.Apparently, we should first update cur's value before passing it into checking!!!while (map.containsKey(cur++)) { //    map.put(cur, 0);    count++;}cur = 0 in the arraycheck cur == 0, cur++ (1), enter the loop,  map.set(1, 0)....The the infinite loop produced.Fixes:1. while (map.containsKey(++cur)) {    map.put(cur, 0);    count++;}2.while (map.containsKey(cur+1)) {    cur++;    map.put(cur, 0);    count++;}
      
     

Solution:

public class Solution {    public int longestConsecutive(int[] nums) {        if (nums == null || nums.length == 0)            return 0;        HashMap
     
       map = new HashMap
      
        ();        for (int i = 0; i < nums.length; i++)            map.put(nums[i], 1);        int max = 0;        for (int i = 0; i < nums.length; i++) {            int cur = nums[i];            int count = 1;            if (map.get(cur) != 0) {                //map.put(cur, 0);                while (map.containsKey(++cur)) {                    map.put(cur, 0);                    count++;                }                cur = nums[i];                while (map.containsKey(--cur)) {                    map.put(cur, 0);                    count++;                }            }            if (count > max)                max = count;        }        return max;    }}