128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-consecutive-sequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

两个哈希表
连续区间头表+连续区间尾表

100来到的过程
头表加入(100,1),1为长度
尾表加入(100,1)

加入3

加入4,查看有没有能连接的区间

查看头表,发现3,将3与4连起来,变成(3,2),代表从3出发,可以连成2个长度的区间
查看尾表,发现3,将3与4连起来,变成(4,2),代表以4为结尾,可以连成2个长度的区间

每个数来的时候都自己建出自己的区间，看看跟之前都不能合，看看后面能不能合，
你每次都严严格格的合完之后，你问我最后有多长的连续区间，你随便找-张表，把value最大值拿出来
每一个数来到的时候，对于哈希表的操作都是0(1)

代码

两个哈希表的版本

    public static int longestConsecutive2(int[] nums) {
        HashMap<Integer, Integer> headMap = new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> tailMap = new HashMap<Integer, Integer>();
        HashSet<Integer> visited = new HashSet<>();
        for (int num : nums) {
            if (!visited.contains(num)) {
                visited.add(num);
                headMap.put(num, 1);
                tailMap.put(num, 1);
                if (tailMap.containsKey(num - 1)) {
                    int preLen = tailMap.get(num - 1);
                    int preHead = num - preLen;
                    headMap.put(preHead, preLen + 1);
                    tailMap.put(num, preLen + 1);
                    headMap.remove(num);
                    tailMap.remove(num - 1);
                }
                if (headMap.containsKey(num + 1)) {
                    int preLen = tailMap.get(num);
                    int preHead = num - preLen + 1;
                    int postLen = headMap.get(num + 1);
                    int postTail = num + postLen;
                    headMap.put(preHead, preLen + postLen);
                    tailMap.put(postTail, preLen + postLen);
                    headMap.remove(num + 1);
                    tailMap.remove(num);
                }
            }
        }
        int ans = 0;
        for (int len : headMap.values()) {
            ans = Math.max(ans, len);
        }
        return ans;
    }

一个哈希表

    public static int longestConsecutive(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int len = 0;
        for (int num : nums) {
            if (!map.containsKey(num)) {
                map.put(num, 1);
                int preLen = map.containsKey(num - 1) ? map.get(num - 1) : 0;
                int posLen = map.containsKey(num + 1) ? map.get(num + 1) : 0;
                int all = preLen + posLen + 1;
                map.put(num - preLen, all);
                map.put(num + posLen, all);
                len = Math.max(len, all);
            }
        }
        return len;
    }