Slide Window 专题

992. Subarrays with K Different Integers

给定一个正整数数组，计算刚好有K个不同数的子数组的个数。(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)

解法一：slide window

 如果是求最多有K个不同元素的子数组，那么就是典型的slide window的题目，只需要在这个典型题目上增添一步：

exactly(K) = atMost(K) - atMost(K-1)

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        //cout<<atMost(A, K)<<" "<<atMost(A, K-1)<<endl;
        return atMost(A, K) - atMost(A, K-1);
    }

    int atMost(vector<int> &A, int K){
        map<int, int> count;
        int ret = 0, win_size = 0, len = A.size(), ctr = 0;
        for(int i=0; i<len; i++){
            if(count[A[i]] == 0){
                ctr++;
            }
            count[A[i]]++;
            while(ctr > K){
                if((--count[A[i-win_size--]]) == 0)
                    ctr--;
            }
            ++win_size;
            //cout<<i<<" "<<win_size<<endl;
            ret += (win_size);
        }
        return ret;
    }
};

View Code

解法二：prefix slide window

思路：

如果子数组[j, i]包含K个不同元素，并且前prefix个元素也出现在子数组[j+prefix, i]中，那么可以得到1+prefix个符合要求的子数组。例如，[1, 2, 1, 2, 3]，前两个数[1, 2]也出现在子数组[1,2,3]中，可以得到1+2

个符合要求的子数组，[1, 2, 1, 2, 3], [2, 1, 2, 3] 和 [1, 2, 3].

遍历数组，维护滑动窗口，窗口尾指向当前元素，窗口头head移动至j，使A[j]在窗口中只出现一次。换句话说，在保证不同元素数不变的情况下，尽量缩短窗口。为达到这个目的，对出现在窗口中元素进行计数，当下一个元素添加到窗口尾时，从窗口头移除尽量多的元素，直至窗口头指向的元素仅在窗口中出现一次，在移除元素的同时，递增prefix。

如果窗口中存在K个不同元素，可以得到1+prefix个符合要求的子数组。

如果窗口中有K+1个不同元素，我们需要移除窗口头指向的元素（该元素仅出现在窗口头），因为我们开始计算一组新的子数组所以重置prefix。

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        int len = A.size(), prefix = 0, head = 0, ret = 0;
        map<int, int> count;
        for(int i=0; i<len; i++){
            if(!count[A[i]]++)
                K--;
            if(K < 0){
                --count[A[head++]];
                prefix = 0;
                K++;
            }
            while(count[A[head]] > 1){
                --count[A[head++]];
                prefix++;
            }
            if(K==0)
                ret += prefix+1;
        }
        return ret;
    }
};

View Code

类似题目：

1248. Count Number of Nice Subarrays

解法一：slide window

exactly(K) = atMost(K) - atMost(K-1)

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        return atMost(nums, k) - atMost(nums, k-1);
    }
    int atMost(vector<int> &nums, int k){
        int len = nums.size(), ret = 0, head = 0;
        for(int i=0; i<len;i++){
            if(nums[i]%2)
                k--;
            while(k<0){
                if(nums[head++]%2)
                    k++;
            }
            ret += i-head+1;
        }
        return ret;
    }
};

View Code

解法二：prefix slide window

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int len = nums.size(), head = 0, ret = 0, prefix = 0;
        for(int i=0; i<len; i++){
            if(nums[i]%2)
                k--;
            if(k<0){
                head++;
                k++;
                prefix = 0;
            }
            while(head<=i && nums[head]%2==0){
                head++;
                prefix++;
            }
            if(k==0)
                ret += prefix+1;
            //cout<<k<<" "<<prefix<<endl;
        }
        return ret;
    }
};

View Code