先給題
給定一個正整數陣列 A，如果 A 的某個子陣列中不同整數的個數恰好為 K，則稱 A 的這個連續、不一定獨立的子陣列為好子陣列，

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

回傳 A 中好子陣列的數目，

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/subarrays-with-k-different-integers
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

1.暴力破解

這個也就不詳談了，一個一個去比較，結果肯定超時，

2.自己想的

當我看到子陣列時，我想到了滑動視窗的解法，之前我也做過這樣的題了，在https://www.cnblogs.com/lisuhang/p/14386502.html，沒看的可以看一下，
我個人的解法其實是對暴力的一種優化，（做的題太少，沒有想到關鍵點）
假設此時我們的子陣列是[i，j]，那么下一個j+1，如何判斷[i，j + 1]符不符合題意呢？讓第j+1個元素與前面出現過的元素比較，如果沒出現過，那么sum++，出現過則sum的值不變，
接下來只要判斷sum的值符不符合K了，如果符合，那么我們可以繼續向右邊滑動，如果不符合，那么我們就要左邊滑動縮小范圍，
原理上是這樣的，但當我們左指標滑動時，去除的那個數對sum的值有沒有影響呢？我們還需要再判斷，如果依次比較，太耗時間了，我在這里想了一個影響值的設定，
影響值是對sum的影響值，打個比方，一開始有一個1，那么這個1 對sum的影響值 就是1，它的加入上sum++了，接下來變成1 2，2與1不同，所以2的影響值也是1，1的影響值不變，接下來變成 1 2 1，那么此時第一個1的影響值就變為0，因為它的加入是不影響sum的值的，
然后我們在保證每時每刻子陣列第一位數的影響值始終是1，那么只要做視窗移動，sum的值一定會受到影響，
如果僅這樣做，我們會丟掉一些符合條件的子陣列，就拿上面的例子 1 2 1 如果K=2，那么符合的子陣列有三個 1 2，2 1，1 2 1.而按照我的影響值，結果就成了1 2和2 1，忽略掉了 1 2 1，那么我們怎么來解決這個問題呢？
我加了一個zero的值來記錄我們到底忽略了前面影響值為0的元素數目，只要是因為首元素影響值為0而左視窗移動的，我們就讓zero++（影響值為0，加不加都不會影響sum值，但加上它也是一個符合的子陣列），只有因為sum>k 而左視窗移動時，zero重置為0（因為此時我們跳過了一個影響值為1的元素，此時是超過K了，所以前面的zero所記錄的值就沒有用了），
接下來就是影響值如何設定了，我們需要右視窗指標指向的元素數值從j-1開始到i依次比較，只要遇到相同的那么就把匹配到的這個元素的影響值設為0，停止回圈，并給右端元素的影響值賦值為1，此時sum值不變；如果沒遇到，那么sum++，
我們知道，當左視窗移動而右視窗沒有移動的時候，此時我們無需再判斷影響值，那么只要是右視窗移動，而且j的值在規定范圍中，我們便讓它去判斷影響值，否則不去判斷，
int subarraysWithKDistinct(vector<int>& A, int K) {
if (K == 0) return 0;
int n = 0;//記錄好子陣列的數量
int sum = 0;//記錄當前子陣列的不同元素個數之和
int zero = 0;
int* sum_add = new int[A.size()];
int i = 0, j = 0;
int flag = 1;
sum_add[i] = 1;
while (i <= j) {
if (flag) {
for (int s = j - 1; s >= i; s--) {
if (A[j] == A[s]) {
sum_add[s] = 0;
sum--;//后面sum++,因為有相同的，sum就不再改變，所以這里讓它--;
break;
}
}
sum++;
sum_add[j] = 1;
}
while (sum_add[i] == 0) {
i++;
zero++;
}
if (sum == K)
n += zero + 1;
if (sum <= K && j < A.size() - 1) {
j++;
flag = 1;
}
else {
zero = 0;
sum--;
i++;
flag = 0;
}
}
return n;
}
這是我寫的代碼，因為越界問題，做了很久，（晚上靜了靜才終于搞定了），
通過是通過了，而且記憶體方面也沒太大問題，但是速度方面卻只是勉強通過，

3.理解題解

剛看題解有點蒙，自己基礎不牢靠過于著急了（每日一題是hard就很難受），
對于雙指標的理解和適用范圍我還不夠了解，本題當中是我們用雙指標的想法解決的不是恰好的問題，而是最多的問題，

來源https://leetcode-cn.com/problems/subarrays-with-k-different-integers/solution/k-ge-bu-tong-zheng-shu-de-zi-shu-zu-by-l-ud34/

那么如何求指定范圍中有多少個最大不同個數為K的子陣列呢？
我們用動態規劃想一下，當[a,b,c]符合題意，[a,b,c,d]加入d后，多出了哪些子陣列？d,c d,b c d,a b c d，right - low +1，（https://leetcode-cn.com/problems/subarrays-with-k-different-integers/solution/c-hua-dong-chuang-kou-li-jie-right-left-vzp76/ ，從這里受教的）
那么這樣就簡單了，每一次移動好后，讓記錄的值加上右邊界減去左邊界+1，就是移動后新增加的符合題意的子陣列了，
class Solution {
public:
int atMostKDistinct(vector<int>& A, int K) {
vector<int> a(A.size() + 1, 0);//a用來記錄A中出現的每個元素的次數，
cout << endl;
int i = 0, j = 0;
int sum = 0;
int r = 0;
while (j < A.size()) {
if (a[A[j]] == 0)
sum++;
a[A[j]]++;
j++;
while (sum > K) {
a[A[i]]--;
if (a[A[i]] == 0)
sum--;
i++;
}
r += j - i;
}
cout << r << endl;
return r;
}
int subarraysWithKDistinct(vector<int>& A, int K) {
return atMostKDistinct(A, K) - atMostKDistinct(A, K - 1);
}
};
這是修改后的代碼

標籤：其他

上一篇：【十天自制軟渲染器】DAY 04：Z-buffering

下一篇：如何用阿里云ECS搭建網站