首页 🍒LeetCode,🐶算法

题目

给定一个正整数数组 A,如果 A 的某个子数组中不同整数的个数恰好为 K,则称 A 的这个连续、不一定独立的子数组为好子数组。

(例如,[1,2,3,1,2] 中有 3 个不同的整数:1,2,以及 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].
示例 2:

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

提示:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/subarrays-with-k-different-integers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

把「恰好」改成「最多」就可以使用双指针一前一后交替向右的方法完成,这是因为 对于每一个确定的左边界,最多包含 KK 种不同整数的右边界是唯一确定的,并且在左边界向右移动的过程中,右边界或者在原来的地方,或者在原来地方的右边。

而「最多存在 KK 个不同整数的子区间的个数」与「恰好存在 K 个不同整数的子区间的个数」的差恰好等于「最多存在 K - 1K−1 个不同整数的子区间的个数」。

因为原问题就转换成为求解「最多存在 KK 个不同整数的子区间的个数」与 「最多存在 K - 1K−1 个不同整数的子区间的个数」,它们其实是一个问题。

思路借鉴:
作者:LeetCode
链接:https://leetcode-cn.com/problems/subarrays-with-k-different-integers/solution/k-ge-bu-tong-zheng-shu-de-zi-shu-zu-by-l-ud34/

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        return atMostKDistinct(A, K) - atMostKDistinct(A, K - 1);
    }

    int atMostKDistinct(vector<int>& A, int K) {
        vector<int> arr(A.size() + 1, 0);
        int left = 0, right = 0;
        int res = 0;
        int count = 0;
        while (right < A.size()) {
            if (arr[A[right]] == 0) {
                count++;
            }
            arr[A[right]]++;
            right++;
            while (count > K) {
                arr[A[left]]--;
                if (arr[A[left]] == 0) {
                    count--;
                }
                left++;
            }
            res += right - left;
        }
        return res;
    }
};



文章评论