在C ++中将数组拆分为连续的子序列

假设我们有一个以升序排序的数组nums。当且仅当我们可以将其拆分为1或多个子序列，使得每个子序列由连续的整数组成且长度至少为3时，我们才必须返回true。因此，如果输入类似于[1,2,3,3,4， 4,5,5]，则输出为True，因为我们有两个连续的序列。它们是[1,2,3,4,5]和[3,4,5]。

为了解决这个问题，我们将遵循以下步骤-

• 制作一个映射m并将nums的频率存储到m中，将nums的大小存储到m中

• cnt：= n

• 对于i，范围为0至n – 1

• 将cnt减小1，将m [x]减小1，将x增大1

• x：= nums [i]

• 如果m [x]和m [x + 1]和m [x + 2]

• 将m [x]，m [x + 1]和m [x + 2]减1，将x减3，将计数减3

• 而m [x]> 0和m [x]> m [x – 1]

• 如果cnt为0，则返回true，否则返回false

• 让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool isPossible(vector<int>& nums) {
      unordered_map <int, int> m;
      int n = nums.size();
      for(int i = 0; i < n; i++){
         m[nums[i]]++;
      }
      int cnt = n;
      for(int i = 0; i < n; i++){
         int x = nums[i];
         if(m[x] && m[x + 1] && m[x + 2]){
            m[x]--;
            m[x + 1]--;
            m[x + 2]--;
            x += 3;
            cnt -= 3;
            while(m[x] > 0 && m[x] > m[x - 1]){
               cnt--;
               m[x]--;
               x++;
            }
         }
      }
      return cnt == 0;
   }
};
main(){
   vector<int> v = {1,2,3,3,4,4,5,5};
   Solution ob;
   cout << (ob.isPossible(v));
}

输入项

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

输出结果

1