【刷题笔记11】滑动窗口-双指针

// 904.水果成篮
// 求解K个不同整数的子数组，最大长度是多少。
int totalFruit(vector<int>& tree, int K) {
    int n = tree.size();
    int left = 0;
    int right = 0;
    
    vector<int> mp(n, 0);
    int ans = INT_MIN;
    int count = 0;
    while (right < n) {
        if (mp[tree[right]] == 0) {
            count++;
        }
        mp[tree[right]]++;
        while (count > K) {
            mp[tree[left]]--;
            if (mp[tree[left]] == 0) {
                count--;
            }
            left++;
        }
        right++;
        ans = max(ans, right - left); // 
    }
    return ans;

}
           

// 795. 区间子数组个数, 注意K的取值
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
    return maxK(nums, right) - maxK(nums, left - 1);
}
int maxK(vector<int>& nums, int k) {
    int left = 0;
    int right = 0;
    int ans = 0;
    int n = nums.size();
    while (right < n) {
        if (nums[right] > k) {
            right++;
            left = right;
            continue;
        }
        right++;
        ans += right - left;
    }
    return ans;        
}


// 992. K 个不同整数的子数组。求解恰好等于K个不同整数的子数组个数
// 把「恰好」改成「最多」就可以使用双指针一前一后交替向右的方法完成。
// 这是因为 对于每一个确定的左边界，最多包含 KK种不同整数的右边界是唯一确定的，并且在左边界向右移动的过程中，右边界或者在原来的地方，或者在原来地方的右边。
// 最多 - 最多 = 恰好
// 而「最多存在 KK 个不同整数的子区间的个数」与「恰好存在 K 个不同整数的子区间的个数」的差恰好等于「最多存在 K - 1K−1 个不同整数的子区间的个数」。


int subarraysWithKDistinct(vector<int>& nums, int k) {

    return maxK(nums, k) - maxK(nums, k - 1);
}

int  maxK(vector<int>& nums, int k)
{
    vector<int> mp(nums.size() + 1, 0);

    int left = 0;
    int right = 0;
    int count = 0; 
    int res = 0;
    while (right < nums.size()) {
        if (mp[nums[right]] == 0) {
            count++;
        }
        mp[nums[right]]++;
        right++;

        while (count > k) {
            mp[nums[left]]--;
            if (mp[nums[left]] == 0) {
                count--;
            }
            left++;
        }
        res += right - left; // 为什么用子数组的长度即right - left来表示增加的子数组个数呢？
    }
    return res;
}
/* 
为什么可以新用子数组的长度即right - left来表示增加的子数组个数呢？
可以借鉴动态规划的思想，举个例子就好理解了：
当满足条件的子数组从[A,B,C]增加到[A,B,C,D]时，新子数组的长度为4，同时增加的子数组为[D],[C,D],[B,C,D],[A,B,C,D]也为4。
*/