LC-992. K 个不同整数的子数组（滑动窗口）

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].
1
2
3

示例 2：

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

提示：

• 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;
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34