求解思路
这道题将"恰好k种"这个条件转化为两个"最多k种"的问题相减。
我们可以这样理解：
如果我们知道有多少个子数组最多包含k种不同数字,再减去最多包含k-1种不同数字的子数组个数,剩下的就是恰好包含k种不同数字的子数组。
想象有一个可伸缩的窗口在数组上滑动,右指针不断向右扩展窗口,每次加入一个新数字就用计数器记录它出现的次数,如果这个数字是第一次出现就让种类数加1。
当窗口内的数字种类超过k时,我们就移动左指针收缩窗口,同时减少对应数字的计数,如果某个数字的计数变为0就让种类数减1,直到窗口内的种类数重新满足不超过k的条件。
在这个过程中,每当右指针固定在某个位置时,从左指针到右指针之间的所有子数组都是满足条件的,所以每次我们把当前窗口的长度也就是r-l+1累加到答案中。
这样遍历完整个数组后,就得到了所有最多包含k种不同数字的子数组总数。
代码实现上,我们使用一个计数数组cnts来记录每个数字在当前窗口中出现的次数,用collect变量维护当前窗口内不同数字的种类数。
通过这种方式,只需要遍历两遍数组分别计算"最多k种"和"最多k-1种",然后做个减法就能得到"恰好k种"的答案。
完整代码
publicstaticintsubarraysWithKDistinct(int[]arr,intk){