659. 分割数组为连续子序列

给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个长度至少为 3 的子序列，其中每个子序列都由连续整数组成。

如果可以完成上述分割，则返回 true ；否则，返回 false 。

 

示例 1：

输入: [1,2,3,3,4,5]
输出: True
解释:
你可以分割出这样两个连续子序列 : 
1, 2, 3
3, 4, 5
示例 2：

输入: [1,2,3,3,4,4,5,5]
输出: True
解释:
你可以分割出这样两个连续子序列 : 
1, 2, 3, 4, 5
3, 4, 5

 

class Solution {
    public boolean isPossible(int[] nums) {
        /**
        贪心:
            开两个Hash表,然后一个存每个元素出现的数量,另一个放 当前元素作为子序列的结尾 的次数
                遍历灭一个元素,x
                    1 先看他的x-1连续子序列存在吗,存在的话让他的x-1子序列-1,当前元素作为末尾, x序列+1
                    2 不存在的话,让当前元素作为开头,看下他的x+1 x+2元素存在吗,
                        不存在,返回false
                        存在,让他们出现的次数都-1,x+2作为序列的末尾元素+1
         */

        Map<Integer,Integer> count=new HashMap();
         Map<Integer,Integer> end=new HashMap();

         for(int n:nums) count.put(n,count.getOrDefault(n,0)+1);//先放元素的次数

         for(int n:nums){
             if(count.getOrDefault(n,0)==0) continue;
             if(end.getOrDefault(n-1,0)>0){
                 //说名他前面存在连续 子序列  当前元素-1
                 count.put(n,count.getOrDefault(n,0)-1);
                 end.put(n-1,end.getOrDefault(n-1,0)-1);//让他的前一个元素作为结尾的序列-1
                 end.put(n ,end.getOrDefault(n ,0)+1);//让他的 作为结尾的序列+1
             }else{
                 //他前面不存在连续子序列
                 //自己作为开头
               if(count.getOrDefault(n+1,0)>0&&count.getOrDefault(n+2,0)>0){
                   //构造完毕 ,让他们出现的次数都-1,x+2作为序列的末尾元素+1
                   end.put(n+2,end.getOrDefault(n+2,0)+1);
                   count.put(n,count.getOrDefault(n,0)-1);
                   count.put(n+1,count.getOrDefault(n+1,0)-1);
                   count.put(n+2,count.getOrDefault(n+2,0)-1);
               }else{
                   //不能构造
                   return false;
               }
             }
         }
         return true;
    }
}