128. Longest Consecutive Sequence

Description

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.

思路与解答

这种查找类型的题目，非要要求时间复杂度为O(n)，那只能牺牲空间复杂度了，这就是此种类型题目的突破口，这里给出在leetcode上看到的几种解法，当然我是觉得第三种方法最好，不过其它比较好理解

第一种解法

参考：https://www.cnblogs.com/grandyang/p/4276225.html
将数组放到set中，目的是去重，然后对数组中的每个元素遍历，对取出的元素，在set中删除该元素以及和该元素相连的元素，并计算长度，继续遍历，直到set中没有元素为止；注意这种解法是时间复杂度是O(n)，因为remove会将set中的元素删除掉，而遍历的是set，while也针对的是set

public int longestConsecutive(int[] nums) {
    int res = 0;
    Set<Integer> s = new HashSet<Integer>();
    for (int num : nums) s.add(num);
    for (int num : nums) {
        if (s.remove(num)) {
            int pre = num - 1, next = num + 1;
            while (s.remove(pre)) --pre;
            while (s.remove(next)) ++next;
            res = Math.max(res, next - pre - 1);
        }
    }
    return res;
}

第二种解法

参考：https://discuss.leetcode.com/topic/15383/simple-o-n-with-explanation-just-walk-each-streak
确实很好，相当于第一种的简化，同样要去重，对于数组中的每个元素，只找与其右相连的序列长度，显然是可以找到最长的序列，但是这个程序如果我写的话肯定是O(n^2)的复杂度，该程序的巧妙之处在于如果数组中的元素在数组中存在与其相连的左边序列，则不对该元素分析，这样就将时间复杂度变为O(n)了

def longestConsecutive(self, nums):
    nums = set(nums)
    best = 0
    for x in nums:
        if x - 1 not in nums:
            y = x + 1
            while y in nums:
                y += 1
            best = max(best, y - x)
    return best

第三种解法

参考：https://discuss.leetcode.com/topic/6148/my-really-simple-java-o-n-solution-accepted
这个方法实际上是维持一些有序序列，每次将数组当前元素(主要是为了后面的重复元素)和该元素对应的序列的边界值进行更新(put)
就拿[4,0,-4,-2,2,5,2,0,-8,-8,-8,-8,-1,7,4,5,5,-4,6,6,-3]这个例子举例
遍历数组，如到7的时候，出现的序列有[4,5],[-4],[-2,-1,0],[2],[-8]
到6的时候，序列为[4,5],[-4],[-2,-1,0],[2],[-8],[7]
到-3的时候，序列为[4,5,6,7],[-4],[-2,-1,0],[2],[-8]
最后生成的序列为[4,5,6,7],[-4],[-3,-2,-1,0],[2],[-8]
理解了上面的原理，下面的代码只是用Hash实现这个过程而已

public int longestConsecutive(int[] nums) {
    HashMap<Integer,Integer> hashMap=new HashMap<>();
    int res=0;
    for(int i:nums){
        if(!hashMap.containsKey(i)){
            int left=hashMap.containsKey(i-1)?hashMap.get(i-1):0;
            int right=hashMap.containsKey(i+1)?hashMap.get(i+1):0;
            int sum=left+right+1;
            hashMap.put(i,sum);
            res=Math.max(res,sum);
            hashMap.put(i-left,sum);
            hashMap.put(i+right,sum);
        }
    }
    return res;
}