1. 题目

给你一个按升序排序的整数数组 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

贪心。

当 x 在数组中时，如果存在一个子序列以 x-1 结尾，长度为 k，则可以将 x 加入该子序列中，得到长度为 k+1的子序列。如果不存在以 x-1结尾的子序列，则必须新建一个只包含 x 的子序列，长度为 1。

对于数组中的元素 x，如果存在一个子序列以 x-1 结尾，则可以将 x 加入该子序列中。将 x 加入已有的子序列总是比新建一个只包含 x 的子序列更优，因为前者可以将一个已有的子序列的长度增加 1，而后者新建一个长度为 1 的子序列，而题目要求分割成的子序列的长度都不小于 3，因此应该尽量避免新建短的子序列。

引入哈希表count、seq

count [i] = j 表示当前数字i在数组中还剩下j个没有放入满足要求的序列

seq [i] = j 表示长度为i的满足要求的序列已有j个

3. 代码

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int,int> count,seq;
        for(auto &x: nums) count[x]++;
        for(auto &x: nums){
            int cnt = count[x];
            if(!cnt)  continue;
            int preSeqCnt = seq[x-1]; 
            if(preSeqCnt){//存在一个子序列以 x-1 结尾，则将 x 加入该子序列中
                count[x]--;
                seq[x-1]--;
                seq[x]++;
            }else{//否则要新起一个子序列
                int sufNum1cnt = count[x+1];
                int sufNum2cnt = count[x+2];
                if(sufNum1cnt && sufNum2cnt){
                    count[x]--;
                    count[x+1]--;
                    count[x+2]--;
                    seq[x+2]++;
                }else return false;
            }
        }
        return true;
    }
};