NC95：数组中的最长连续子序列

方法1：排序
方法2：Set
方法3：哈希表
方法4：并查集

解法1：排序+统计

1. 排序数组

2. 统计连续序列长度：遇到重复元素跳过；遇到不连续元素重置；遇到连续元素加一并更新max

   import java.util.*;
   public class Solution {
    /**
     * max increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int MLS (int[] arr) {
        if(arr == null || arr.length == 0){
            return 0;
        }
   
        int len = arr.length;
        Arrays.sort(arr);
        int count = 1;
        int result = 1;
        for(int i=0;i<len-1;i++){
            if(arr[i+1] - arr[i] == 1){
                count++;
            }else if(arr[i+1] - arr[i] == 0){
                continue;
            }else{
                count = 1;
            }
   
            result = Math.max(count, result);
        }
   
        return result;
    }
   }

解法2：使用set集合

准备一个HashSet，将所有元素入set，之后遍历数组中的每一个数num

• 如果num - 1存在于set中，那么num不可能是左边界，直接跳过
• 如果num - 1不存在于set中，那么num会是一个左边界，我们再不断地查找num+1、num+2......是否存在于set中，来看以num为左边界的连续序列能有多长

在上述遍历中，我们知道了对于每一个可能的左边界，能扩出的最长连续序列的长度，再在这些长度中取最大即为结果。

• 时间复杂度：O(n)，其中 n 为数组的长度。
  外层循环需要 O(n)的时间复杂度，只有当一个数是连续序列的第一个数的情况下才会进入内层循环，然后在内层循环中匹配连续序列中的数，因此数组中的每个数只会进入内层循环一次。根据上述分析可知，总时间复杂度为 O(n)

• 空间复杂度：O(n)。哈希表存储数组中所有的数需要 O(n) 的空间

  import java.util.*;
  public class Solution {
    public int MLS (int[] arr) {
        if(arr.length == 0)
            return 0;
        int n = arr.length;
        int max = 1;
        Set<Integer> set = new HashSet<>();
        for(int num:arr)
            set.add(num);   //先将数组中的值都存储在set集合中
        for(int num:arr){
            if(set.contains(num-1)) continue; 
             //如果集合中包含比当前值小1的，则结束本次循环
  
            int start = num;   
            //不存在比当前值小1的，则去寻找以当前值开始的连续子序列
            while(set.contains(start+1)){
                start++;
            }
            //得到较长的子序列
            max = Math.max(max,start-num+1);
        }
        return max;
    }
  }

  解法3：哈希表

链接：https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/fang-fa-cong-yi-dao-nan-bing-cha-ji-fang-fa-bu-hui/

哈希表的value存什么

• key存数字，value存什么？
• 新存入的数字，如果它找到相邻的数，它希望从邻居数那里获取什么信息？
• 很显然它希望，左邻居告诉它左边能提供的连续长度，右邻居告诉它右边能提供的连续长度
• 加上它自己的长度，就有了自己处在的连续序列的长度

  

  更新新序列的两端数字的value
• 同处一个连续序列的数字的value理应都相同，这是它们共同特征
• 但没有必要每个的value都是序列长度，只需要两端的数存序列的长度就好
• 因为靠的是两端和新数对接，序列是连续的，中间没有空位
• 序列的一端找到邻居后，将另一端对应的value更新为最新的序列长度
  

  public int MLS (int[] arr) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int max = 0;
        for(int num : arr)
        {
            if(!map.containsKey(num))
            {
                int preLen = map.get(num-1) == null ? 0 : map.get(num-1);
                int nextLen = map.get(num+1) == null ? 0 : map.get(num+1);
                int curLen = preLen + 1 + nextLen;
                map.put(num, curLen);
                max = Math.max(max, curLen);
                map.put(num - preLen, curLen);
                map.put(num + nextLen, curLen);
            }
        }
        return max;
    }

解法4：并查集

链接：https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/javacong-bao-li-fa-dao-zi-shang-er-xia-dong-tai-gu/
用并查集的话，就是每次union的时候，更新子树size，每次更新也更新最大值len，union到最后一个元素后，就能返回答案了

class Solution {
    Set<Integer> checkInNums = new HashSet<>();
    class UF {
        // 记录树的“重量”
        private int maxValue = 1;
        // 存储⼀棵树
        private Map<Integer, Integer> parent = new HashMap<>();
        private Map<Integer, Integer> size = new HashMap<>();
        public UF(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                parent.put(nums[i], nums[i]);
                size.put(nums[i], 1);
            }
        }
        public void union(int p, int q) {
            if(!checkInNums.contains(p) || !checkInNums.contains(q))
                return;
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ)
                return;
            // ⼩树接到⼤树下⾯，较平衡
            if (size.get(rootP) > size.get(rootQ)) {
                parent.put(rootQ, rootP);
                size.put(rootP, size.get(rootP)+size.get(rootQ));
                maxValue = Math.max(maxValue, size.get(rootP));
            } 
            else {
                parent.put(rootP, rootQ);
                size.put(rootQ, size.get(rootP)+size.get(rootQ));
                maxValue = Math.max(maxValue, size.get(rootQ));
            }
        }
        private int find(int x) {
            while (parent.get(x) != x) {
                int tmp = parent.get(x);
                //进⾏路径压缩
                parent.put(x, parent.get(tmp));
                x = tmp;
            }
            return x;
        }
        public int findMax() {
            return maxValue;
        }
    }

    public int longestConsecutive(int[] nums) {
        if(nums.length == 0)
            return 0;
        UF uf = new UF(nums);
        for(int i = 0; i < nums.length; i++)
            checkInNums.add(nums[i]);
        for(int i = 0; i < nums.length; i++)
            uf.union(nums[i], nums[i]-1);
        return uf.findMax();
    }
}