【题目】
给定无序数组arr，返回其中最长的连续序列的长度
举例，arr=[100，4，200，1，3，2]，最长的连续序列为[1，2，3，4]，所以返回4
【分析】
HashMap是一种存储键值对(key-value)的数据结构，基于哈希表实现Map接口。可以使用这种数据结构来寻找最长连续序列的长度
首先生成一个HashMap的实例map，其中key表示数组元素，value表示该元素所在连续序列的长度。从头开始遍历数组，如果元素arr[i]不在map中，则将(arr[i], 1)放入map中，代表目前arr[i]单独作为一个连续序列，然后查看map中是否有arr[i]-1，如果有，则说明arr[i]-1所在的连续序列可以和arr[i]合并，合并后记为A序列，利用map可以得到A序列的长度，记为lenA，序列的左边界元素记为leftA，右边界元素记为rightA，只在map中更新合并后的序列的相关信息，即两个边界信息和长度信息，更新成(leftA, lenA)和(rightA, lenA)；再查看map中是否有arr[i]+1，如果有，说明arr[i]+1所在的连续序列可以和序列A合并，合并后记为B序列。通过map可以得到B序列的长度，记为lenB，序列B的左边界元素记为leftB，右边界元素记为rightB，只在map中更新合并后序列的相关信息，即两个序列边界信息和长度信息，更新成(leftB, lenB)和(rightB, lenB)。遍历过程中用一个全局变量max记录每次合并后，所有连续序列中长度的最大值，即为最长连续序列的长度。
遍历过程中只需要更新合并后序列的两个边界信息和序列长度信息，因为我们判断两个序列是否可以合并，是根据这两个序列的边界信息判断的，和这两个序列的中间元素无关，所以对于这两个序列的中间元素，不用更新其value值。
1 public int longestConsecutive(int[] arr) 2 { 3 if(arr == null || arr.length == 0) 4 { 5 return 0; 6 } 7 8 HashMap<Integer, Integer> map = new HashMap<>(); 9 int max = 1; 10 11 for(int i = 0; i < arr.length; i++) 12 { 13 if(!map.containsKey(arr[i])) 14 { 15 map.put(arr[i], 1); 16 if(map.containsKey(arr[i]-1)) // 如果map中存在arr[i]-1，说明arr[i]可以和arr[i]-1所在的序列合并 17 { 18 max = Math.max(max, merge(map, arr[i]-1, arr[i])); 19 } 20 if(map.containsKey(arr[i]+1)) // 如果map中存在arr[i]+1，说明arr[i]所在的序列可以和arr[i]+1所在的序列合并 21 { 22 max = Math.max(max, merge(map, arr[i], arr[i]+1)); 23 } 24 } 25 } 26 return max; 27 } 28 29 public int merge(HashMap<Integer, Integer> map, int less, int more) 30 { 31 int left = less - map.get(less) + 1; // 合并后连续序列的左边界 32 int right = more + map.get(more) - 1; // 合并后连续序列的右边界 33 int len = right - left + 1; // 合并后连续序列的长度 34 map.put(left, len); // 更新合并后连续序列的左边界元素的value，即左边界元素所在连续序列的长度 35 map.put(right, len); // 更新合并后连续序列的右边界元素的value，即右边界元素所在连续序列的长度 36 return len; 37 } 38
来源：左程云老师《程序员代码面试指南》
"Coding Interview Guide" -- 数组中的最长连续序列
原文：https://www.cnblogs.com/latup/p/10881444.html