数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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，
定义一个集合 current
j := 0，ans := 0，n := a 的大小
定义一个映射 m
对于初始化 i := 0，当 i < a 的大小，更新（将 i 增加 1），执行 -
如果 m[a[i]] 为零，则将 m[a[i]] 增加 1 -
当 k < 0 时，执行 -
如果将 m[a[j]] 减少 1 且 m[a[i]] 为零，则 -
(将 k 增加 1)
(将 j 增加 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
更新于: 2020-06-04
183 次查看
广告