题目参见这里 https://leetcode.com/problems/longest-consecutive-sequence/
这个题目我感觉很难，看了半天别人写的答案，才明白个所以然。下面的代码是我自己的改编，写的好像很复杂的样子，主要也是为了方便自己理解，耐着性子看完，应该就理解了。
【个人分析】：
题目难度主要是要求O(N)完成。本来最自然的想法是先排序然后再去扫一遍得到结果，可是这样，明显就是O(NlgN)。怎么样从NlgN 提高到O(N)呢？ ==> 空间换时间，空间从O(1) 变成 O(N) ==> 变成O(N)的空间的话，首推哈希表 ==> 如果是用哈希表的话，用序列中的数字做 map 中的 key 是比较自然的想法，所以问题就集中到了，用什么来做 map 中的 value 上来。
【代码注释】：
上面的主线基本只能推进到那里了，剩下的就是对题目本身的挖掘。我在这里用的是类似动态规划里面常用的前缀、后缀的那种思路。新建了一个类 Bound 来作为 map 中的value , （当然可以不用新建类，直接用一个 list 来做。新建一个类是为了写起来清楚）。对于map中的一个值 num, 它对应的value 是Bound, Bound.maxRangeAsLeftBound 是说，到目前为止，以 num 作为一个连续序列的左边界的所有可能中最长的那个，maxRangeAsRighgBound类似的道理。举个例子，如果有 map[3] = {maxRangeAsLeftBound = 2, maxRangeAsRightBound=3}, 那么就是说存在连续序列【3，4】，和连续序列【1，2，3】
这个算法的精髓，我个人认为，在于只抓一个范围的两头，对于在范围里面的数字置之不理。什么意思？ 假设数组是【4，3，1，2】 ，在依次处理完4，3，1之后，我们要处理2，加入2之后，整个数组中，最长的连续序列将变成，【1-4】。此时，我们只需要更新1，和 4在map中对于的value, 而对于3，这个数夹在1-4之间，对于它在map中的value，我们不必再费神去更新。
为什么？ 你想嘛，假设后面出现了一个更长的序列，是以3 作为左边界，即 maxRange = [3,...], 那么让1做这个范围的边界岂不是可以得到一个更长的【1，2，3...]？ 同样的道理，如果maxRange = [...3], 那么让4作为这个范围的右边界，范围也会变得更长。所以，我们不会再用到 3 在map 中对应的 value， 所以也就不用再去更新它了。
正是因为这样，整个算法的复杂度才是O(N), 如果对于任意一个数字，都要去更新range中所有数字对应的value,那么复杂度就会变成平方。
【实际例子】: int[] nums = {4,1,3,2}, int resultExpected = 4
| 数组中的数字(num) | 左邻数字是否存在 | 以num作为右边界的最长序列 | 右邻数字是否存在 | 以num作为左边界的最长序列 | 包含该数字的最长连续序列 | 更新 | 更新后Map |
| 4 | 3存在吗？ 否 | [4] | 5存在吗? 否 | [4] | [4] U [4] = [4] | m[4]={l:1,r:1} | {4：{l:1,r:1}} |
| 1 | 0存在吗？ 否 | [1] | 2存在吗？否 | [1] | [1] U [1] = [1] | m[1]={l:1,r:1} |
{4：{l:1,r:1}} {1:{l:1, r:1}} |
| 3 | 2存在吗? 否 | [3] | 4存在吗？是 | [3，4] | [3] U [3,4] = [3,4] |
m[3]={l:2,r:1} m[4].r = 2 m[3].l = 2 (3,4是包含3的最大范围的两端边界) |
{4: {l: 1, r: 2}} {1:{l: 1, r: 1}} {3:{l: 2,r: 1}} |
| 2 | 1存在吗？是 | [1,2] | 3存在吗? 是 | [2,3,4] | [1,2]U[2,3,4] = [1,2,3,4] |
m[2]={l:3,r:2} m[4].r = 4 m[1].l = 4 (1,4是包含2的最大范围的两端边界) |
{4: {l: 1, r: 4}} {1:{l:4,r:1}}, {3:{l:2,r:1}}, {2:{l:3,r:2}} |
public class Solution {
public int longestConsecutive(int[] nums) {
int result = 0;
Map<Integer, Bound> rangeMap = new HashMap<Integer, Bound>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if ( !rangeMap.containsKey(num) ) {
int maxRangeToThisNumber = 1;
int maxRangeFromThisNumber = 1;
// can this number be a right boundary of a range ?
if (rangeMap.containsKey(num - 1)) {
maxRangeToThisNumber += rangeMap.get(num - 1).maxRangeAsRightBound;
}
// can this number be a left boundary of a range?
if (rangeMap.containsKey(num + 1)) {
maxRangeFromThisNumber += rangeMap.get(num + 1).maxRangeAsLeftBound;
}
int maxRangeIncludeThisNumber =
maxRangeToThisNumber + maxRangeFromThisNumber - 1;
// update range map
Bound bound = new Bound(maxRangeFromThisNumber, maxRangeToThisNumber);
rangeMap.put(num, bound);
// num is not the right boundary of max range including num
if (maxRangeFromThisNumber != 1) {
// update the range of number at the right bound
int rightEnd = maxRangeFromThisNumber + num - 1;
Bound boundRight = rangeMap.get(rightEnd);
boundRight.maxRangeAsRightBound = maxRangeIncludeThisNumber;
rangeMap.put(rightEnd, boundRight);
}
if (maxRangeToThisNumber != 1) {
int leftEnd = num - maxRangeToThisNumber + 1;
Bound boundLeft = rangeMap.get(leftEnd);
boundLeft.maxRangeAsLeftBound = maxRangeIncludeThisNumber;
rangeMap.put(leftEnd, boundLeft);
}
// update global max
result = Math.max(result, maxRangeIncludeThisNumber);
}
}
return result;
}
public class Bound {
public int maxRangeAsRightBound = 0;
public int maxRangeAsLeftBound = 0;
public Bound(int _maxRangeAsLeftBound, int _maxRangeAsRightBound) {
maxRangeAsLeftBound = _maxRangeAsLeftBound;
maxRangeAsRightBound = _maxRangeAsRightBound;
}
}
}