659

https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences/solution/
分割数组为连续子序列 给你一个按升序排序的整数数组 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]

转载：

算法思路
首先使用两个哈希mapnc和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了
因此，只有检查到某个数时，这个数未被消耗完，且既不能和前面组成连续子序列，也不能和后面组成连续子序列时，无法分割

复杂度分析
时间复杂度：O(N)O(N)，所有元素遍历一遍O(N)O(N)，循环内部均为常数时间操作O(1)O(1)
空间复杂度：O(N)O(N)，使用了两个哈希map
举例
以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

作者：aspenstarss
链接：https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences/solution/tan-xin-suan-fa-jian-cha-shu-zu-neng-fou-bei-fen-w/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:unordered_map<int,int> nc,tail;bool isPossible(vector<int>& nums) {for(auto num:nums){nc[num] ++;}for(auto num:nums){if(nc[num]==0) continue;else if( nc[num]>0 && tail[num-1]>0){tail[num-1]--;tail[num]++;nc[num]--;}else if(nc[num]>0 && nc[num+1]>0 && nc[num+2]>0){tail[num+2]++;nc[num]--;nc[num+1]--;nc[num+2]--;}elsereturn false;}return true;}
};