首页 > 试题广场 >

合法连续子段

[编程题]合法连续子段
  • 热度指数：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].
算法知识视频讲解
开通博客
头像 不想看论文
发表于 2022-03-26 09:44:20
滑动窗口——java版 用两个指针表示窗口的左边界（i）和有边界（j），用map存储窗口中每个元素出现的次数，当窗口中的元素满足条件时，则从窗口的左边界到右边界之后的所有区间也都满足条件。 (i, j) (i, j+1) (i, j+2) .......... (i, n -1) 区间数为 n - 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 CUG23届硕士毕业生
发表于 2022-04-12 10:46:45
简单滑动窗口算法 题目简述 长度为n的数组a，求有多少个存在某元素出现次数 >= m 的连续子区间[l,r] 算法分析 我们可以发现： 若子区间[i,j]不满足情况，固定i不动，j每次后移一步，一次添加一个元素，直到恰好满足 num[a[j]] == m 时，所有以i为起点，以j后面为终点的区 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 wolverine12138
发表于 2022-01-05 21:42:48
滑动窗口 滑动窗口的核心在于维护窗口的左指针和右指针的移动条件，有时可以一次移动多位，有时只能移动一位。移动多位的条件要求跳过的情况已经被覆盖，本例左指针一次移动多位。 #include<iostream> #include<vector> #include<unord 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 阿里巴巴 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
22条回答 7428浏览

热门推荐

通过挑战的用户

相关试题

合法连续子段

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号