Force deduction exercise - 26 split array into continuous subsequences

26 Split the array into successive subsequences

1. Problem 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 .

Example 1：

Input : [1,2,3,3,4,5]

Output : True

explain :

You can separate these two consecutive subsequences :

1, 2, 3

3, 4, 5

Example 2：

Input : [1,2,3,3,4,4,5,5]

Output : True

explain :

You can separate these two consecutive subsequences :

1, 2, 3, 4, 5

3, 4, 5

Example 3：

Input : [1,2,3,4,4,5]

Output : False

explain ：

The input array length range is [1, 10000]

2. Enter description
First type num The length of n, Then input n It's an integer
3. The output shows that
Output “true” or “false”, Exclude Quotes .
4. Example
Input
8
1 2 3 3 4 4 5 5
Output
true
5. Code

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_map>
using namespace std;

bool isPossible(vector<int>& nums) {
    
	//1. Use two hash tables nc and tail
	//cnt[i]  Store the numbers in the original array i Number of occurrences 
	//tail[i] Store in i The number of consecutive subsequences at the end and in line with the meaning of the question 

	unordered_map<int, int> cnt, tail;//unordered_map: Its implementation uses a hash table  ; and  map The implementation uses a red black tree 

	//2. Count the number of times 
	for (auto num : nums)
		cnt[num]++;

	//3. Traverse   Only when a certain number is checked , This number has not been consumed , And it cannot form a continuous subsequence with the front , Nor can it form a continuous subsequence with the following , Cannot divide 

	for (auto num : nums)
	{
    
		if (cnt[num] == 0) continue;
		else if (cnt[num] > 0 && tail[num - 1] > 0) //tail[num-1]>0 Represents the tail of the preceding continuous subsequence to num-1 ; If at this time  num  At least one  , Then the subsequence can be extended 
		{
    
			cnt[num]--;//num Number of occurrences minus one 
			tail[num - 1]--;// With num-1 Subtract one from the number of consecutive subsequences at the end 
			tail[num]++;// With num Add one to the number of consecutive subsequences at the end 
		}
		else if (cnt[num] > 0 && cnt[num + 1] > 0 && cnt[num + 2] > 0)  // There are continuous subsequences 
		{
    
			cnt[num]--;
			cnt[num + 1]--;
			cnt[num + 2]--;
			tail[num + 2]++;
		}
		else
			return false;
	}
	return true;
}
int main()
{
    
	int n,tmp; 
	cin >> n;
	vector<int>nums;
	for (int i = 0; i < n; i++)
	{
    
		cin >> tmp;
		nums.push_back(tmp);
	}
	bool res = isPossible(nums);
	//true The return value is 1 false  The return value is 0
	res == 1 ? (cout << "true") : (cout << "false");
	return 0;
}