分割数组为连续子序列

[xszi]

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

[xszi]

首先使用两个哈希 map：nc和tail

• nc[i]：存储原数组中数字i出现的次数
• tail[i]：存储以数字i结尾的且符合题意的连续子序列个数

1. 先去寻找一个长度为3的连续子序列 i, i+1, i+2，找到后就将 nc[i], nc[i+1], nc[i+2] 中对应数字消耗1个（即-1），并将 tail[i+2] 加 1，即以 i+2 结尾的子序列个数 +1。
2. 如果后续发现有能够接在这个连续子序列的数字 i+3，则延长以 i+2 为结尾的连续子序列到 i+3，此时消耗 nc[i+3] 一个，由于子序列已延长，因此tail[i+2] 减 1，tail[i+3] 加 1
3. 在不满足上面的情况下:

• 如果 nc[i] 为 0，说明这个数字已经消耗完，可以不管了
• 如果 nc[i] 不为 0，说明这个数字多出来了，且无法组成连续子序列，所以可以直接返回 false 了

因此，只有检查到某个数时，这个数未被消耗完，且既不能和前面组成连续子序列，也不能和后面组成连续子序列时，无法分割

举例

以 nums=[1,2,3,3,4,4,5] 为例

• 初始化：nc[1] = 1、nc[2]=1、nc[3]=2、nc[4]=2、nc[5]=1，tail[i]都为0
• 检查数字 1, nc[1]>0,并且 nc[2]>0,nc[3]>0，因此找到了一个长度为3的连续子序列 nc[1]、nc[2]、nc[3] 各自减一，并 tail[3] 加 1，此时有：

nc[1] = 0、nc[2]=0、nc[3]=1、nc[4]=2、nc[5]=1
tail[3]=1

• 检查数字 2，发现 nc[2] 为 0，跳过（已经被消耗完了）
• 检查数字 3，发现 nc[3]>0,但是 tail[2]=0，因此不能接在前面，只能往后看(如果后面组不成，那就返回 false了),实际发现 nc[4]>0,nc[5]>0，因此找到了一个长度为3的连续子序列 nc[3]、nc[4]、nc[5] 各自减一，并 tail[5] 加 1，此时有:

nc[1] = 0、nc[2]=0、nc[3]=0、nc[4]=1、nc[5]=0
tail[3]=1、tail[5]=1

• 检查第二个数字 3，nc[3]=0，跳过
• 检查数字 4，nc[4]>0，又有 tail[3]>0，说明有一个以3结尾的连续子序列，因此可以将其延长，所以nc[4]减1，tail[3]减1,tail[4]加1,此时有:

nc[1] = 0、nc[2]=0、nc[3]=0、nc[4]=0、nc[5]=0
tail[3]=0、tail[4]=1、tail[5]=1

• 检查数字 5，nc[5]=0，跳过
• 遍历完所有数字，返回 true。

const isPossible = (nums) => {
    let max = nums[nums.length - 1]
   // nc：存储原数组中数字每个数字出现的次数
   // tail：存储以数字num结尾的且符合题意的连续子序列个数
   let nc = new Array(max + 2).fill(0), 
       tail = new Array(max + 2).fill(0)
    for(let num in nums){
        nc[num]++;
    }
    
    for(let num in nums){
        if(nc[num] == 0) continue;
        else if(tail[num-1] > 0){
            tail[num-1]--;
            tail[num]++;
        }else if(nc[num+1] > 0 && nc[num+2] > 0){
            nc[num+1]--;
            nc[num+2]--;
            tail[num+2]++;
        }else{
            return false;
        }
        nc[num]--;
    }
    return true;
}