书籍数组中的最长连续序列（4）0716

题目
给定无序数组arr，返回其中最长的连续序列的长度。

一些定义：

数组

子数组： 一个或连续多个数组中的元素组成一个子数组。子数组最少包含一个元素。

对于大小为n的数组，有n*(n+1)/2个非空子数组。

子序列：子序列就是在原来序列中找出一部分组成的序列，子序列不一定来连续，相对位置还是不变。但是，在数学中，某个序列的子序列是从最初序列通过去除某些元素单补破坏余下元素的相对位置（在前或在后）而形成的新序列。

对于大小n的序列，总共可以有（2n次幂 -1）个非空子序列。

1.生成哈希表HashMap map,key代表遍历过的某个数，value代表key这个数所在的最长连续序列的长度。同时map还可以表示arr中的一个数之前是否出现过。

2.从左到右遍历arr，假设遍历到arr[i]。如果arr[i]之前出现过，直接遍历下一个数，只处理之前没出现过的arr[i]。首先在map中加入记录(arr[i],1)，代表目前arr[i]单独作为一个连续序列。然后看map中是否含有arr[i]-1，（因为map中存的值序列是连续的，所以看arr[i] - 1 和 arr[i] + 1），如果有，则说明arr[i]-1所在的连续序列可以和arr[i]合并，合并后记为A序列。利用map可以得到A学历低饿长度，记为lenA，最小值记为leftA，最大值记rightA，只在map中更新与leftA和rightA有关的记录，更新成（leftA，lenA）和（rightA，lenA）。接下来看map中是否含有arr[i] + 1,如果有，则说明arr[i] +1所在的连续序列可以和A合并，合并后记为B序列。利用map可以得到B序列的长度为lenB，最小值记录为leftB，最大值记为rightB，只在map中更新与leftB和rightB有关的记录，更新成（leftB，lenB）和（rightB，lenB）。

3.遍历的过程中用全局变脸max记录每次合并出的序列的长度最大值，最后返回max。

public int longestConsecutive(int[] arr){
    if(arr == null || arr.length == 0){
        return 0;
    }
    int max = 1;
    HashMap map = new HashMap();
    for(int i = 0;i
        if(!map.containsKey(arr[i])){
            map.put(arr[i],1);
            if(map.containsKey(arr[i] - 1)){
                max = Math.max(max,merge(map,arr[i] - 1),arr[i]);
            }
            if(map.containsKey(arr[i] + 1)){
                max = Math.max(max,merge(map,arr[i],arr[i]-1));
            }
        }
    }
    return max;
}
 
public int merge(HashMap map, int less ,int more){
    int left = less  - map.get(less) + 1;
    int right = more + map.get(more) - 1;
    int len = right - left +1;
    map.put(left,len);
    map.put(right,len);
    return len;
}