C ++中具有K个不同整数的子数组

假设我们有一个由正整数组成的数组A，如果子数组中不同整数的个数正好是K，则可以调用A的一个好子数组（连续的）。因此，如果该数组像[1,2,3,1 ，2]具有3个不同的整数：1、2和3。我们必须找到A的良好子数组的数量。

因此，如果输入类似于[1,2,3,1,4]且K = 3，则输出将为4，因为它可以形成具有四个完全不同的整数的三个子数组，它们分别为[1,2,3 ]，[1,2,3,1]，[2,3,1]，[3,1,4]。

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

• 定义一个函数atMost()，它将采用数组a和变量k，

• 定义一组电流

• j：= 0，ans：= 0，n：= a的大小

• 定义一张映射

• 对于初始化i：= 0，当i <a的大小时，更新（将i增加1），执行-

• 当k <0时，-

• （将k增加1）

• 如果m [a [j]]减少1并且m [a [i]]为零，则-

• （将j增加1）

• 如果m [a [i]]为零，则将m [a [i]]加1，然后-

• x：=（(i-j)+ 1）

• ans：= ans + x

• 返回ans

• 从主要方法中执行以下操作-

• 返回atMost(a,k)-atMost(a,k-1);

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

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int subarraysWithKDistinct(vector<int>& a, int k) {
      return atMost(a, k) - atMost(a, k - 1);
   }
   int atMost(vector <int>& a, int k){
      set <int> current;
      int j = 0;
      int ans = 0;
      int n = a.size();
      unordered_map <int, int> m;
      for(int i = 0; i < a.size(); i++){
         if(!m[a[i]]++) k--;
         while(k < 0){
            if(!--m[a[j]])
            k++;
            j++;
         }
         int x = ((i - j) + 1);
         ans += x;
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,1,4};
   cout << (ob.subarraysWithKDistinct(v, 3));
}

输入项

{1,2,3,1,4}, 3

输出结果

4