[LeetCode] 992. Subarrays with K Different Integers #992

grandyang · 2019-05-30T16:29:44Z

Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.

(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)

Return the number of good subarrays of A.

Example 1:

Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

Example 2:

Input: A = [1,2,1,3,4], K = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Note:

1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length

这道题给了一个只有正整数的数组A，然后定义了一种好子数组，需要该子数组中不同的数字的个数正好为给定的正数K。这种玩子数组个数的题目，如果是求极值，大概率是要用动态规划做，不过这里是求满足某个条件的子数组的个数，还有一种比较常见的解法，就是滑动窗口 Sliding Window，这是一种非常重要的解题思路，也经常在面试中出现，所以务必需要掌握。LeetCode 中关于滑动窗口的题还蛮多的，可以参见下方的类似题目区域，列出了一堆堆。在不遍历所有子数组的情况下，求正好有K个不同的数字并不是很容易，这道题需要稍稍转换一下思维，比较好求的求最多有K个不同的数字的情况。若能分别求出最多有K个不同数字的子数组的个数，和最多有 K-1 个不同数字的子数组的个数，二者相减，就是正好有K个不同数字的子数组的个数。我们之前做过这样一道题目 Longest Substring with At Most K Distinct Characters，求最多有K个不同字符的最长子串，这里就是用的相同的滑动窗口的思路来做。

由于要同时求K和 K-1 的情况，所以可以用个子函数来做。在 helper 函数中，使用一个 HashMap 来建立每个数字和其出现次数之间的映射，再用个变量 left 标记窗口的左边界。下面进行 for 循环，若当前的数字没出现过，则K自减1，因为此时子数组中多了一个不同的数字，然后该数字的映射值自增1。此时K值有可能小于0了，说明子数组中的不同数字过多了，需要移除一个，用个 while 循环，若K小于0则进行循环，此时左边界上的数字的映射值自减1，减小后若为0了，则说明该数字已经彻底被移出了滑动窗口，此时K应该自增1，同时左边界 left 自增1，表示向右移动一位。此时这个窗口的长度就代表了此时最多有k个不同数字的子数组的个数，将其加入结果 res，这样直至 for 循环退出后，就可以得到最终的结果了，参见代码如下：

解法一：

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        return helper(A, K) - helper(A, K - 1);
    }
    int helper(vector<int>& A, int K) {
        int n = A.size(), res = 0, left = 0;
        unordered_map<int, int> numCnt;
        for (int i = 0; i < n; ++i) {
            if (numCnt[A[i]] == 0) --K;
            ++numCnt[A[i]];
            while (K < 0) {
                if (--numCnt[A[left]] == 0) ++K;
                ++left;
            }
            res += i - left + 1;
        }
        return res;
    }
};

滑动窗口有多种写法，比如下面这种并不直接减小K，而是用 HashMap 中的映射个数来跟K比较，不过这样的话就一定要移除不在窗口内的映射才行，参见代码如下：

解法二：

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        return helper(A, K) - helper(A, K - 1);
    }
    int helper(vector<int>& A, int K) {
        int n = A.size(), res = 0, left = 0;
        unordered_map<int, int> numCnt;
        for (int i = 0; i < n; ++i) {
            ++numCnt[A[i]];
            while (numCnt.size() > K) {
                if (--numCnt[A[left]] == 0) numCnt.erase(A[left]);
                ++left;
            }
            res += i - left + 1;
        }
        return res;
    }
};

再来看另一种写法，这里建立的是数字和其下标之间的映射，而不是其出现的个数，不过整体的思路并没有啥太大的区别，参见代码如下：

解法三：

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        return helper(A, K) - helper(A, K - 1);
    }
    int helper(vector<int>& A, int K) {
        int n = A.size(), res = 0, left = 0;
        unordered_map<int, int> num2idx;
        for (int i = 0; i < n; ++i) {
            num2idx[A[i]] = i;
            while (num2idx.size() > K) {
                if (num2idx[A[left]] == left) num2idx.erase(A[left]);
                ++left;
            }
            res += i - left + 1;
        }
        return res;
    }
};

Github 同步地址:

#992

类似题目：

Number of Substrings Containing All Three Characters

Count Number of Nice Subarrays

Replace the Substring for Balanced String

Max Consecutive Ones III

Binary Subarrays With Sum

Fruit Into Baskets

Shortest Subarray with Sum at Least K

Minimum Size Subarray Sum

Longest Substring with At Most Two Distinct Characters