leetcode 659. 分割数组为连续子序列-Toy模板网

这篇具有很好参考价值的文章主要介绍了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]–文章来源地址https://www.toymoban.com/news/detail-788934.html

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;
    }
};