LeetCode659.分割数组为连续子序列 (哈希表)

题目描述

给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为 3 。

一个子序列是从原始数组挑选一部分（也可以全部）元素而不改变相对位置形成的新数组

如果可以完成上述分割，则返回 true ；否则，返回 false 。

说明：

输入的数组长度范围为 [1, 10000]

输入样例1

8
1 2 3 3 4 4 5 5

输出样例1

true

解释:

你可以分割出这样两个连续子序列 :
1, 2, 3

3, 4, 5

输入样例2

6
1 2 3 4 4 5

输出样例2

false

分析

本题目采取贪心的思路，我们首先用一个哈希表mp1记录所有数字出现的次数，之后用另外一个哈希表mp2来表示长度至少为3的序列的是否存在。
如果当前数为x，如果mp2[x-1]存在，就把这个数接到x-1后面，同时更新mp2中以x-1结尾和以x结尾的序列个数。
若x-1的序列不存在，就重新开一个序列，但需要判断x+1，x+2是否存在。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n;
class Solution {
public:
    bool isPossible(vector<int>& nums) {
        map<int,int> mp1,mp2;
        for(auto x:nums) mp1[x]++;  //记录所有数字的出现次数
        for(auto x:nums)
        {
            if(!mp1[x]) continue;   //如果这个数用完了，就跳过本轮循环
            if(mp2[x-1]){   //如果以x-1的序列存在，就把x加到末尾
                mp2[x]++;
                mp2[x-1]--;
                mp1[x]--;
            }
            else if(mp1[x+1] && mp1[x+2])   //若x-1的序列不存在，就重新开一个序列，但需要判断x+1，x+2是否存在
            {
                mp2[x+2]++; //创建一个以x开头，x+2结尾的序列
                mp1[x]--,mp1[x+1]--,mp1[x+2]--;
            }
            else return false;
        }
        return true;
    }
};
int main()
{
    
    cin>>n;
    vector<int> v;
    int a;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        v.push_back(a);
    }
    
    if(Solution().isPossible(v)) puts("true");
    else puts("false");
    
    return 0;

}