Leetcode659. split the array into continuous subsequences (hash table)

Title Description

Here's an array of integers sorted in ascending order num（ May contain duplicate numbers ）, Please divide them into one or more subsequences , Each subsequence is composed of continuous integers with a length of at least 3 .

A subsequence is a selection of parts from the original array （ Or all of them ） Element without changing its relative position

If the above segmentation can be completed , Then return to true ; otherwise , return false .

explain ：

The input array length range is [1, 10000]

sample input 1

8
1 2 3 3 4 4 5 5

sample output 1

true

explain :

You can separate these two consecutive subsequences :
1, 2, 3

3, 4, 5

sample input 2

6
1 2 3 4 4 5

sample output 2

false

analysis

This topic adopts greedy thinking , We first use a hash table mp1 Record the number of occurrences of all numbers , Then use another hash table mp2 To indicate that the length is at least 3 Whether the sequence of exists .
If the current number is x, If mp2[x-1] There is , Just connect this number to x-1 Back , Simultaneous updating mp2 China and Israel x-1 End and end with x The number of sequences at the end .
if x-1 The sequence of does not exist , Just reopen a sequence , But it needs judgment x+1,x+2 Whether there is .

C++ Code

#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]++;  // Record the number of occurrences of all numbers 
        for(auto x:nums)
        {
            if(!mp1[x]) continue;   // If this number runs out , Just skip this cycle 
            if(mp2[x-1]){   // If the x-1 The sequence of exists , Just put x Add to the end 
                mp2[x]++;
                mp2[x-1]--;
                mp1[x]--;
            }
            else if(mp1[x+1] && mp1[x+2])   // if x-1 The sequence of does not exist , Just reopen a sequence , But it needs judgment x+1,x+2 Whether there is 
            {
                mp2[x+2]++; // Create a to x start ,x+2 The sequence at the end 
                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;

}