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


题目描述：


输入一个按升序排序的整数数组（可能包含重复数字），你需要将它们分割成几个子序列，其中每个子序列至少包含三个连续整数。返回你是否能做出这样的分割？


 


示例 1：



输入: [1,2,3,3,4,5]

输出: True

解释:

你可以分割出这样两个连续子序列 :

1, 2, 3

3, 4, 5


#### 大家一起斗地主啦！



解法参考题解区大佬，两个hash 加 贪心


/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isPossible = function(nums) {
    
    let counter = new Array(10000).fill(0);
    let end = new Array(10000).fill(0);
    
    //以上实现两个hash(网上实现hash太费劲了，取了个巧，浪费了点空间) 
    
    //先把每种牌的总数记下
    nums.forEach((item)=>{
        counter[item] ++;
    })
    
    
    // nums.forEach((item)=>{
    //forEach 没法continue
    
    //以下采取贪心策略：
    for(let i = 0 ;i<nums.length;i++){
        let item = nums[i];
        if(counter[item] === 0){//这种牌没得了，直接下一个
            continue;
        }
        counter[item] --;
        
        if(end[item-1] > 0){ //可以续上先续上
            end[item-1] --;
            end[item] ++;
        }
        
        //因为是升序排列，所以如果有[1,2,3,4,4,5，6]时
        //先是4接上[1,2,3],然后另外一个4连上后头的，组成[4,5,6]
        //关键在数组已经按升序排序
        else if(counter[item+1] > 0 && counter[item+2] > 0){
            counter[item+1] --;
            counter[item+2] --;
            end[item+2] ++;
        }
        else{
            return false;
        }
        
        
    };
    return true;
    
    
};