首页 > 试题广场 >

合法连续子段

[编程题]合法连续子段

热度指数：2327 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小强有一个长度为 $n$ 的数组 $a$ 和正整数 $m$ .
他想请你帮他计算数组 $a$ 中有多少个连续子区间[l,r],其区间内存在某个元素出现的次数不小于 $m$ 次?
例如数组 $a=[1,2,1,2,3]$ 且 $m =2$ ,那么区间[1,3],[1,4],[1,5],[2,4],[2,5]都是满足条件的区间,但区间[3,4]等都是不满足条件的.

输入描述:

第一行输入两个正整数和.
第二行输入n个正整数.

输出描述:

输出一个整数表示答案.

示例1

输入

5 2
1 2 1 2 3

输出

说明

满足条件的区间为[1,3],[1,4],[1,5],[2,4],[2,5].

算法知识视频讲解

Python

__kk__

双指针

from collections import defaultdict
n, m = list(map(int, input().split()))
arr = list(map(int, input().split()))

mem = defaultdict(int)
ans = 0
i,j = 0,0
max_num = 0

while j < n:
    mem[arr[j]] += 1
    max_num = max(max_num, mem[arr[j]])
    if max_num == m:
        while max_num == m:
            ans += n-j
            if mem[arr[i]] == max_num:
                max_num -= 1
            mem[arr[i]] -= 1
            i += 1
    j+=1
print(ans)

发表于 2022-03-08 18:43:44 回复(0)