leetcode怎么解決K 個不同整數(shù)的子數(shù)組

這篇文章主要介紹“l(fā)eetcode怎么解決K 個不同整數(shù)的子數(shù)組”，在日常操作中，相信很多人在leetcode怎么解決K 個不同整數(shù)的子數(shù)組問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”leetcode怎么解決K 個不同整數(shù)的子數(shù)組”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

一、題目內(nèi)容

給定一個正整數(shù)數(shù)組 A，如果 A 的某個子數(shù)組中不同整數(shù)的個數(shù)恰好為 K，則稱 A 的這個連續(xù)、不一定獨立的子數(shù)組為好子數(shù)組。

（例如，[1,2,3,1,2] 中有 3 個不同的整數(shù)：1，2，以及 3。）

返回 A 中好子數(shù)組的數(shù)目。

示例 1：

輸入：A = [1,2,1,2,3], K = 2
輸出：7
解釋：恰好由 2 個不同整數(shù)組成的子數(shù)組：[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 個不同整數(shù)組成的子數(shù)組：[1,2,1,3], [2,1,3], [1,3,4].

提示：

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

二、解題思路

最多存在 K 個不同整數(shù)的子區(qū)間的個數(shù)與恰好存在K個不同整數(shù)的子區(qū)間的個數(shù)的差恰好等于最多存在 K - 1個不同整數(shù)的子區(qū)間的個數(shù)。

因此，最多存在 K 個不同整數(shù)的子區(qū)間的個數(shù) - 最多存在 K - 1個不同整數(shù)的子區(qū)間的個數(shù) = 恰好存在K個不同整數(shù)的子區(qū)間的個數(shù)。

三、代碼

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

    # 計算最多為K的子數(shù)組長度
    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)

到此，關(guān)于“l(fā)eetcode怎么解決K 個不同整數(shù)的子數(shù)組”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>