給定一個正整數陣列 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
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路：
子陣列恰好K個不同整數的子陣列個數，可以理解為小于等于K個不同整數的子陣列個數-小于等于K-1個不同整數的子陣列個數，那么在編程時，只需要撰寫保證保存小于等于K個不同整數的子陣列個數的函式，最后輸入k與k-1，函式值做差即可，代碼如下：
class Solution {
public:
int GetMostDistinct(vector<int>& A, int K) {
unordered_map<int, int> mp;
int left = 0, right = 0, ret = 0;
while (right < A.size()) {
++mp[A[right++]];
while (mp.size() > K) {
--mp[A[left]];
if (mp[A[left]] == 0) mp.erase(A[left]);
++left;
}
// 如果這里改成 ret = max(ret, right - left)，那么此函式就是 LeetCode 904 題的解，
// 這里可以用動態規劃的思想來理解 ret += right - left
// right 增加一次，增加的陣列個數可以用 right - left 來表示
ret += right - left;
}
return ret;
}
int subarraysWithKDistinct(vector<int>& A, int K) {
return GetMostDistinct(A, K) - GetMostDistinct(A, K - 1);
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/258529.html
標籤：其他
上一篇：四、解讀VisualDSP++案例之21489 AD1939 C Block-Based Talkthru 48 or 96 kHz