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