题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n$、$m$、$k(1 \leq k \leq m \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^6)$，长为$m$的数组$b(1 \leq b[i] \leq 10^6)$。

输出$a$有多少个长为$m$的连续子数组$sub$，满足$sub$与$b$的交集大小至少是$k$。交集可以有重复元素。

输入样例

5
7 4 2
4 1 2 3 4 5 6
1 2 3 4
7 4 3
4 1 2 3 4 5 6
1 2 3 4
7 4 4
4 1 2 3 4 5 6
1 2 3 4
11 5 3
9 9 2 2 10 9 7 6 3 6 3
6 9 7 8 10
4 1 1
4 1 5 6
6

输出样例

4
3
2
4
1

算法

哈希表+滑动窗口

比较容易想到滑动窗口，先初始化哈希表$window$和$counter$，前者存$a$数组前$m$个元素的频数信息，后者存$b$数组所有元素的频数信息。对于第一个窗口，先计算两者的交集大小$s=\Sigma_x min(window[x],counter[x])$，其中$x$是$window$和$counter$中的公共元素。

随后滑动窗口来更新$s$和$window$，遍历$r \in [m+1,n]$，$window[a[r]]$会自增，如果自增后满足$window[a[r]] \leq counter[a[r]]$，说明多了一个公共元素，自增$s$。否则增加一个$a[r]$是多余的，并不会增加公共元素。扩张了右边界还需要收缩一下左边界，需要将$a[r-m]$移出窗口，令$l=r-m$，如果$window[a[l]]$自减之后$\lt counter[a[l]]$，说明少了一个公共元素，$s$自减。否则减不减少$a[l]$都能够覆盖住$b$中的所有数值$a[l]$，并不会减少公共元素。

复杂度分析

时间复杂度

初始化第一个窗口需要遍历$a$的前$m$个元素，$b$的全体元素，时间复杂度为$O(m)$。后续的滑动窗口每次改变区间左右端点时更新窗口哈希表的时间复杂度为$O(1)$，滑完整个$a$数组的时间复杂度为$O(n)$。因此，整个算法的时间复杂度为$O(m+n)$。

空间复杂度

空间消耗的瓶颈在于两个哈希表$window$和$counter$，在最差情况下这两个哈希表中最多会存储$m$个键值对，也就是说$b$中所有元素和$a$中所有元素都各不相同。此时的额外空间复杂度为$O(m)$，这也是整个算法的额外空间复杂度。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int n, m, k, a[N], b[N];

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d", &n, &m, &k);
        unordered_map<int, int, custom_hash> window, counter;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            if(i <= m) window[a[i]]++;
        }
        for(int i = 1; i <= m; i++) {
            scanf("%d", &b[i]);
            counter[b[i]]++;
        }
        int s = 0, ans = 0;
        for(auto&[num, freq]: window) {
            s += min(freq, counter[num]);
        }
        if(s >= k) {
            ans++;
        }
        for(int r = m + 1; r <= n; r++) {
            int l = r - m;
            window[a[r]]++;
            if(window[a[r]] <= counter[a[r]]) {
                s++;
            }
            window[a[l]]--;
            if(window[a[l]] < counter[a[l]]) {
                s--;
            }
            if(s >= k) {
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}