首页 > 试题广场 >

合法连续子段

[编程题]合法连续子段
  • 热度指数:2327 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小强有一个长度为的数组和正整数.
他想请你帮他计算数组中有多少个连续子区间[l,r],其区间内存在某个元素出现的次数不小于次?
例如数组,那么区间[1,3],[1,4],[1,5],[2,4],[2,5]都是满足条件的区间,但区间[3,4]等都是不满足条件的.

输入描述:
第一行输入两个正整数.
第二行输入n个正整数.



输出描述:
输出一个整数表示答案.
示例1

输入

5 2
1 2 1 2 3

输出

5

说明

满足条件的区间为[1,3],[1,4],[1,5],[2,4],[2,5].
双指针
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)

热门推荐

通过挑战的用户

合法连续子段