LCP-992 K个不同整数的子数组

题目回顾

题目详情

给定一个正整数数组 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. 1 <= A.length <= 20000
2. 1 <= A[i] <= A.length
3. 1 <= K <= A.length

---

Discussion | Solution

解法思路

滑动窗口月当然还是用滑动窗口的方法。这题乍一看挺简单，随手就敲了一个$O(n^2)$的双指针遍历方法。果然就卡在了超时上了。

要降低时间复杂度就要让指针不回头，但这时还要找到所有恰好有K种整数的情况并不容易。我们不妨转化下问题，要找到符合条件最长的子串是可以一次遍历求解的。那么一个包含K种数字的最长子串的所有子串均包含$\le K$种数字。

因此可以定义一个函数getMostDistinct(A, K)求得含$\le K$种数字的子串个数，那恰好为K个的情况就等于getMostDistinct(A, K)-getMostDistinct(A, K-1)

思路总结：直接求等不好求的时候，可以将等号条件转化为两个不等关系相减

代码实现

/*
 * @lc app=leetcode.cn id=992 lang=cpp
 *
 * [992] K 个不同整数的子数组
 */

// @lc code=start
class Solution {
public:
    int getMostDistinct(vector<int>& A, int K){
        int l=0,r=0;
        int size=A.size();
        int* st=new int[size+1]();
        int cnt=0;
        int res=0;
        while(r<size){
            if(st[A[r]]==0){
                cnt++;
            }
            st[A[r]]++;
            r++;
            while(cnt>K){
                st[A[l]]--;
                if(st[A[l]]==0){
                    cnt--;
                }
                l++;
            }
            res+=r-l;

        }
        return res;
    }

    int subarraysWithKDistinct(vector<int>& A, int K) {
        return getMostDistinct(A,K)-getMostDistinct(A,K-1);
    }
};
// @lc code=end

时间复杂度O(n) 2 2还是O(n)