分割数组为连续子序列

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

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

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

xszi / javascript-algorithms

分割数组为连续子序列 #101