HJ177 可匹配子段计数
知识点双指针
校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
给定整数数组 aa（长度 nn）与数组 bb（长度 mm，m≦nm≦n）。设一个长度为 mm 的数组 cc 被称为可匹配的，当且仅当将 cc 的元素重新排列后，与数组 bb 在对应位置上至少有 kk 个元素相等。
对于 aa 中的每一个长度恰为 mm 的连续子段，都可视为一个候选数组 cc。求满足条件的子段数量。
【形式化解释】
若子段 al..l+m−1al..l+m−1 经重排可与 bb 至少 kk 个位置相等，则称该子段为"可匹配的"。等价地，设 cntx(S)cntx(S) 为元素 xx 在序列 SS 中出现次数，则子段 cc 的"匹配度"为 match(c)=∑xmin(cntx(c), cntx(b))match(c)=∑xmin(cntx(c), cntx(b))，若 match(c)≧kmatch(c)≧k 则符合要求。
输入描述：
第一行输入整数 t(1≦t≦104)t(1≦t≦104)——测试用例组数。
每个测试用例：
• •一行三个整数 n,m,k(1≦k≦m≦n≦2×105)n,m,k(1≦k≦m≦n≦2×105)；
• •一行 nn 个整数 a1…an (1≦ai≦106)a1…an (1≦ai≦106)；
• •一行 mm 个整数 b1…bm (1≦bi≦106)b1…bm (1≦bi≦106)。
输入保证所有测试用例的 nn 之和、mm 之和均不超过 2×1052×105。
输出描述：
对每个测试用例输出一行整数，表示满足条件的子段数量。
示例1
输入：
1 4 1 1 4 1 5 6 6
复制输出：
1
#include <iostream> #include <vector> #include <map> using namespace std; void solve() { int n, m, k; cin >> n >> m >> k; vector<int> a(n); map<int, int> mapB; for (int i = 0; i < n; ++i) { cin >> a[i]; } for (int i = 0; i < m; ++i) { int val; cin >> val; mapB[val]++; } map<int, int> mapA; int current_match = 0; int ans = 0; // 初始化第一个窗口 for (int i = 0; i < m; ++i) { mapA[a[i]]++; } for (auto const& [val, countB] : mapB) { if (mapA.count(val)) { current_match += min(mapA[val], countB); } } if (current_match >= k) { ans++; } // 滑动窗口 for (int i = m; i < n; ++i) { int remove_val = a[i - m]; int add_val = a[i]; // 处理移出窗口的元素 if (mapB.count(remove_val)) { if (mapA[remove_val] <= mapB[remove_val]) { current_match--; } } mapA[remove_val]--; if (mapA[remove_val] == 0) { mapA.erase(remove_val); } // 处理加入窗口的元素 if (mapB.count(add_val)) { if (mapA.count(add_val) < 1 || mapA[add_val] < mapB[add_val]) { current_match++; } } mapA[add_val]++; if (current_match >= k) { ans++; } } cout << ans << endl; } int main() { int t; cin >> t; while (t--) { solve(); } return 0; }