LeetCode 992. K 个不同整数的子数组
2021-02-12 01:16
标签：etc distinct 窗口 复杂度 += 可见 调整 大于 span 困难题，先想着DP扫描，但是会爆栈； 主体思想仍然采用滑动窗口来进行； 但是对于该题目，有一个比较新的点，要利用脑经急转弯思想把问题转换一下； 对于正好为K个不同元素组成的最长字符串可以转换为： 最多由K个不同元素组成的字符串-最多由K-1个不同元素组成的字符串； （这样可以有效的降低复杂度，使得单次区间寻找即可找到符合要求的字符串） 可以想象出，我们只需要寻找K个不同元素组成的字符串即可； 但是针对于该问题，统计字符串个数也有一个小tip； 当我们确定一个字符串为K个不同元素组成的字符串，那么他的子串也必定是对多由K个不同元素的组成的字符串； 因此，每次right和left确定区间，首先要找到当前的最长K个不同元素组成的字符串，然后统计子数组个数，即为right-left+1； 例如：1，2，1，2，4； 对于,1,2,1,2序列，可以有4个子序列： 1，2，1，2 2，1，2 1，2 2 所以可见，正好为k个整数的序列和最多为k个整数的序列都包含在内； 当遇到大于k的序列，立刻调整left指针，重新选找下一个符合条件的序列； 对于序列内不同元素计数，采用map计数即可； LeetCode 992. K 个不同整数的子数组 标签：etc distinct 窗口 复杂度 += 可见 调整 大于 span 原文地址：https://www.cnblogs.com/songlinxuan/p/14394173.htmlclass Solution {
public:
int fun(vectorint>& A, int K) {
mapint, int>mp;
int len = A.size();
int le = 0, ri = 0;
int res = 0;
int dis = 0;
while (ri len) {
if (mp[A[ri]] == 0)
dis++;
mp[A[ri]]++;
while (dis > K) {
mp[A[le]]--;
if (mp[A[le]] == 0) {
dis--;
}
le++;
}
res += ri - le + 1;
ri++;
}
return res;
}
int subarraysWithKDistinct(vectorint>& A, int K) {
return fun(A,K)-fun(A,K-1);
}
};
上一篇：Go语言标准库log介绍