leetcode 659. 分割数组为连续子序列

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