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

迈不过友情╰ 2022-10-07 00:47 119阅读 0赞

> 给你一个按升序排序的整数数组 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;
        }
    }