题解 | 可匹配子段计数

这道题就是滑动窗口，在窗口内检查有没有和b里面元素相同的，有的话就加1，当前窗口遍历结束后检查cnt_same是否>=k，如果满足的话那就可以让ans++(满足条件的字段)。

但是，这道题最坑的地方在于：按这种方法的话，我们要小心，假如a={1 1 1 1 1 1}, b= {1,2,3,4}，那么因为a所有元素都与b第一个元素相等，所以cnt_same会一直自增，但实际上这并不能满足题目：

当且仅当将 c 的元素重新排列后，与数组 b 在对应位置上至少有 k 个元素相等。很明显a的1的次数远远超限了

为此，我们不仅要给b里面的元素出现次数建立一个哈希表，还需要给当前长度为m的滑动窗口里的元素建立哈希表count_same，统计重复的数字到底出现了多少次，是否次数大于b里面相同元素出现的次数呢？这就是一个贡献度的问题了。

那么有了这个哈希表count_same，我们

在给cnt_same( 这个变量的含义是将 c 的元素重新排列后，与数组 b 在对应位置上相等的元素的个数)自增时的条件，就是hash[a[i]] > count_same[a[i]]，

在给cnt_same自减（此时滑动窗口准备向右移动一位，那么左指针指向的元素得被踢出）时，条件就是hash[a[i]] > count_same[a[i]]

保证贡献度不超限的情况下，才让cnt_same自减

#include <ios>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    // 至少有k个元素相等，要查找一个公共子串
    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<int> a(n), b(n);
        unordered_map<int , int> hash,count_same;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < m; i++) {
            cin >> b[i];
            hash[b[i]]++;
        }

        int cnt_same = 0, cnt = 0; // cnt_same统计总共有多少数相同
        for (int i = 0; i < n; i++) {
            if (count_same[a[i]] < hash[a[i]]) {
                cnt_same++;
            }
            count_same[a[i]]++; 
		  
            if (i >= m-1 ) { // i是右指针，大于m-1时滑动窗口正式形成
                if (cnt_same >= k) {
                    cnt++;
                }
			    // i-m+1是左指针，保留着即将被踢出的左窗口元素
                if (count_same[a[i-m+1]] <= hash[a[i-m+1]]) {
                    cnt_same--;
                }
                count_same[a[i-m+1]]--;
			  
            }
        }
        cout << cnt << '\n';
    }
    return 0;
}