题目链接：leetcode 659
1.题目
给你一个按 非递减顺序 排列的整数数组 nums 。
请你判断是否能在将 nums 分割成 一个或多个子序列 的同时满足下述 两个 条件：
每个子序列都是一个 连续递增序列（即，每个整数 恰好 比前一个整数大 1 ）。
所有子序列的长度 至少 为 3 。
如果可以分割 nums 并满足上述条件，则返回 true ；否则，返回 false 。
2.示例
1）示例 1：
输入：nums = [1,2,3,3,4,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,5] --> 1, 2, 3
[1,2,3,3,4,5] --> 3, 4, 5
2）示例 2：
输入：nums = [1,2,3,3,4,4,5,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --> 3, 4, 5
3）示例 3：
输入：nums = [1,2,3,4,4,5]
输出：false
解释：无法将 nums 分割成长度至少为 3 的连续递增子序列。
4）提示：
1 <= nums.length <= 10^4
-1000 <= nums[i] <= 1000
nums 按非递减顺序排列
3.分析
使用两个哈希表，map[i]表示数字i还剩几个，map2[i]表示以i为结尾的子数组的个数
那么对nums的元素（如i）逐个遍历
1）当map1[i]=0时候表示没有再需要使用的i了，那么直接遍历下一个元素
2）当map1[i]>0时，首先考虑是否有i-1为结尾的子数组(map2[i-1]>0)，可以直接添加上去，那么map2[i-1]–,map2[i]++,map1[i]–
3）当不存在i-1为结尾的子数组时候，我们考虑以i为开头，是否还有i+1,i+2可以组成子数组，那么map1[i+2]++,map1[i]–.map1[i+1]–,map1[i+2]–
4.分析
class Solution {
public:
map<int,int> map1;
map<int,int> map2;
bool isPossible(vector<int>& nums) {
for(int i=0;i<nums.size();i++){
map1[nums[i]]=0;map2[nums[i]]=0;
map1[nums[i]+1]=0;map1[nums[i]+2]=0;
}
for(int i=0;i<nums.size();i++)
map1[nums[i]]++;
for(int j=0;j<nums.size();j++){
int i=nums[j];
if(map1[i]==0) continue;
if(map1[i]>0&&map2[i-1]>0){
map2[i-1]--;
map2[i]++;
map1[i]--;
continue;
}
if(map1[i]>0&&map1[i+1]>0&&map1[i+2]>0){
map2[i+2]++;
map1[i]--;map1[i+1]--;map1[i+2]--;
continue;
}
return false;
}
return true;
}
};
