做书架的网站,康定网站建设公司,网站建设与O2O的应用,做公益网站有什么要求给定一个正整数数组 A#xff0c;如果 A 的某个子数组中不同整数的个数恰好为 K#xff0c;则称 A 的这个连续、不一定独立的子数组为好子数组。
#xff08;例如#xff0c;[1,2,3,1,2] 中有 3 个不同的整数#xff1a;1#xff0c;2#xff0c;以及 3。#xff09; …给定一个正整数数组 A如果 A 的某个子数组中不同整数的个数恰好为 K则称 A 的这个连续、不一定独立的子数组为好子数组。
例如[1,2,3,1,2] 中有 3 个不同的整数12以及 3。
返回 A 中好子数组的数目。
示例 1
输入A [1,2,1,2,3], K 2 输出7 解释恰好由 2 个不同整数组成的子数组[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
解题思路
这题与普通滑动窗口的不同之处在于要统计[l,r]区间内的满足不同整数的个数恰好为 K的子数组的个数按照常规滑动窗口做法需要不断l,直到不同整数的个数不为 K但是这样的话新得到的窗口就会丢失一部分元素后面枚举r的时候就会有遗漏。 因此这题不直接移动l而是选择维护一个多重的滑动窗口[l…l1…r]其中[l1,r]区间为满足不同整数的个数恰好为 K-1的区间 设区间末尾都是r 因为[l1…r]是恰好只有k-1个不同整数的所以起始位置在l1前面的子数组区间内的不同整数的个数都大于k-1 因为[l…r]是恰好只有k个不同整数的所以起始位置在l前面的子数组区间内的不同整数的个数都大于k 综上所述起始位置处于l和l1的子数组区间内的不同整数的个数都刚好等于k 因此统计[l,r]区间内的满足不同整数的个数恰好为 K的子数组的个数只需要计算l1-l即可。
代码
class Solution {public int subarraysWithKDistinct(int[] A, int K) {int nA.length;int[] cnt1new int[n1],cnt2new int[n1];int n10,n20,l10,l20;int l0,r0,res0;while (rn){if(cnt1[A[r]]0)n1;cnt1[A[r]];if(cnt2[A[r]]0)n2;cnt2[A[r]];while (n2K-1){cnt2[A[l2]]--;if(cnt2[A[l2]]0)n2--;l2;}while (n1K){cnt1[A[l1]]--;if(cnt1[A[l1]]0)n1--;l1;}resl2-l1;r;}return res;}
}
