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

太过爱你忘了你带给我的痛 2022-12-26 10:17 137阅读 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
     
    
    示例 3：
    
    输入: [1,2,3,4,4,5]
    输出: False
     
    
    提示：
    
    输入的数组长度范围为 [1, 10000]
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
        
        public boolean isPossible(int[] nums) {
        
            Map<Integer,Integer> countMap=new HashMap<>();
            Map<Integer,Integer>end=new HashMap<>();
            for(int num:nums){
        
                int cnt=countMap.getOrDefault(num,0);
                countMap.put(num,cnt+1);
            }
            for(int num:nums){
        
                int cnt=countMap.get(num);
                if(cnt<=0) continue;
                int prev=end.getOrDefault(num-1,0);
                if(prev==0){
        
                    int cnt1=countMap.getOrDefault(num+1,0);
                    int cnt2=countMap.getOrDefault(num+2,0);
                    if(cnt1>0&&cnt2>0){
        
                        countMap.put(num,cnt-1);
                        countMap.put(num+1,cnt1-1);
                        countMap.put(num+2,cnt2-1);
                        end.put(num+2,end.getOrDefault(num+2,0)+1);
                    }
                    else return false;
                }
                else{
        
                    countMap.put(num,cnt-1);
                    end.put(num-1,prev-1);
                    end.put(num,end.getOrDefault(num,0)+1);
                }
            }
            return true;
        }
    }