计算数字出现超过x次的子段数量
计算数字出现超过x次的子段数量
输入: n, x. 表示有数组中有n个数字, 目标出现的次数大于等于x.例如:
7 3
2 1 3 2 1 3 2
输出1, 因为只有1个子段(2 1 3 2 1 3 2)中有数字出现了大于等于3次.
使用滑动窗口(双指针)的方法, 左右指针构成一个窗口(子段). 右指针持续向右走, 同时增加计数, 当满足条件时, 计算此时的子段数量(不同终点). 此时, 移动左指针, 缩小窗口, 记录不同起点的子段数.
int n, x;
cin >> n >> x;
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
int ans = 0;
int l = 0, r = 0;
while (r < n) {
++cnt[nums[r]];
while (cnt[nums[r]] >= x) {
ans += n - r;
--cnt[nums[l]];
++l;
}
++r;
}
cout << ans << endl;