leetcode怎么解决K 个不同整数的子数组

这篇文章主要介绍“leetcode怎么解决K 个不同整数的子数组”，在日常操作中，相信很多人在leetcode怎么解决K 个不同整数的子数组问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”leetcode怎么解决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 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length

二、解题思路

最多存在 K 个不同整数的子区间的个数与恰好存在K个不同整数的子区间的个数的差恰好等于最多存在 K – 1个不同整数的子区间的个数。

因此，最多存在 K 个不同整数的子区间的个数 – 最多存在 K – 1个不同整数的子区间的个数 = 恰好存在K个不同整数的子区间的个数。

三、代码

class Solution:
    def subarraysWithKDistinct(self, A: list, K: int) -> int:
        return self._subarrayWithDistinct(A, K) - self._subarrayWithDistinct(A, K - 1)

    # 计算最多为K的子数组长度
    def _subarrayWithDistinct(self, A, K):
        freq_num = [0 for _ in range(len(A) + 1)]

        left, right = 0, 0
        count = 0
        res = 0

        while right < len(A):
            if freq_num[A[right]] == 0:
                count += 1
            freq_num[A[right]] += 1
            right += 1

            while count > K:
                freq_num[A[left]] -= 1
                if freq_num[A[left]] == 0:
                    count -= 1
                left += 1
            # 长度贡献
            res += right - left
        return res


if __name__ == '__main__':
    s = Solution()
    A = [1, 2, 1, 2, 3]
    K = 2
    ans = s.subarraysWithKDistinct(A, K)
    print(ans)

到此，关于“leetcode怎么解决K 个不同整数的子数组”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！