992. K 个不同整数的子数组

难度困难412

给定一个正整数数组 nums和一个整数 k ，返回 num 中 「好子数组」 的数目。

如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为 「****好子数组 」。

• 例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。

子数组 是数组的 连续 部分。

示例 1：

输入：nums = [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].

示例 2：

输入：nums = [1,2,1,3,4], k = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].

提示：

• 1 <= nums.length <= 2 * 104
• 1 <= nums[i], k <= nums.length

滑动窗口

题解：https://leetcode.cn/problems/subarrays-with-k-different-integers/solution/c-hua-dong-chuang-kou-li-jie-right-left-vzp76/

为什么可以新用子数组的长度即right - left来表示增加的子数组个数呢？

可以借鉴动态规划的思想，举个例子就好理解了：

当满足条件的子数组从[A,B,C]增加到[A,B,C,D]时，新子数组的长度为4，同时增加的子数组为[D],[C,D],[B,C,D],[A,B,C,D]也为4。

建议做一下下面这两道题加深理解

• 904. 水果成篮 和 713. 乘积小于K的子数组

class Solution {public int subarraysWithKDistinct(int[] nums, int k) {int n = nums.length;int[] lower = new int[n],upper = new int[n];find(lower, nums, k);find(upper, nums, k-1);int ans = 0;for(int i = 0; i < n; i++){// upper[i]-lower[i]代表了考虑nums[i]为右边界，// 不同字符数量恰好为k的子数组数量ans += upper[i] - lower[i];}return ans;}//找到 i 左边 最远 满足出现k个不同字符的下标void find(int[] arr, int[] nums, int k){int n = arr.length;int[] cnt = new int[n+1];//sum 记录出现不同字符的个数for(int high = 0, low = 0, sum = 0; high < n; high++){int right = nums[high];if(cnt[right] == 0) sum++;cnt[right]++;while(sum > k){ // 当滑动窗口内有k+1个不同字符时，要弹出一个int left = nums[low++];cnt[left]--;if(cnt[left] == 0) sum--;}arr[high] = low;}}}