题解 | 可匹配子段计数

#include <iostream>
#include <map>
#include <vector>
using namespace std;

//1.需要允许map的value < 0表示超过计数
//2.在i >= m后需要先处理a[i - m]再处理a[i]
int main() {
	int t;
	cin >> t;
	int n, m, k;
	map<int, int> b;
	vector<int> a;
	while (t--) {
		b.clear();
		a.clear();
		cin >> n >> m >> k;
		int tmp;
		for (int i = 0; i < n; i++) {
			cin >> tmp;
			a.push_back(tmp);
		}
		for (int i = 0; i < m; i++) {
			cin >> tmp;
			b[tmp]++;
		}
		int ans = 0, cnt = 0;
		for (int i = 0; i < a.size(); i++) {
			if (i >= m) {
				if (b.find(a[i - m]) != b.end()) {
					if (b[a[i - m]] >= 0) cnt--;
					b[a[i - m]]++;
				}
			}
			if (b.find(a[i]) != b.end()) {
				if (b[a[i]] > 0) cnt++;
				b[a[i]]--;
			}
			if (i >= m - 1) {
				ans += cnt >= k ? 1 : 0;
			} 
		}
		cout << ans << endl;
	} 
}