题目链接: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;}};