在线编程介绍
阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding
本文为大家介绍其中的 第97题：破译密码 的题目解析，具体如下：
题目描述
题目等级：中等
知识点：尺取法
查看题目：破译密码
给你一个长度为n的序列，元素标号1-n。问能够找到多少对不同的（L,R）（1 <= L <= R），使得在子序列[L,R]内存在出现频率不低于K的元素？
输入序列大小n（1 <= n <= 10^4）、出现频率k（1 <= k <= n）和一个包含n个整数的数组，第i个整数表示序列的第i个元素为ai(1 <= ai <= 10^9)。
输出满足条件的子序列个数。
示例1
输入：
4
2
[1 ,2 ,1 ,2]
输出：
3
注意
三个子序列分别为[1,3],[1,4],[2,4]
解题思路:尺取法
与57超级区间那道题是类似的方法。
设当前区间为[L, R]。初始L = R = 0；使用尺取法需要判断什么时候调整L和R。
情况1：假设对于某个区间[L1, R1]满足题目要求。则保持L1不变，依次增加R1直到n为止的所有区间都满足题目的要求。
情况2：假设对于某个区间[L2，R2]不满足题目要求。则需要保持L2不动，增加R2才可能满足满足题目要求。
情况3：是情况2拓展。如果[L2，n]不满足题目要求，则任何i>L2，区间[i, n]都不满足题目要求。
使用一个 2*n 的数组numb来记录当前区间[L, R]内每个元素的出现次数。numbL和numbR表示区间[L, R]对应的numb数组范围。因为每个数都是按照进入区间[L, R]的顺序离开区间[L, R]的，相当于一个队列，所以numb数组可以用numbL和numbR来表示当前区间[L, R]内的元素，而不用考虑中间某个数不在区间[L, R]内的情况。
计算过程
- 初始L = R = 0；sum = 0; 用来计算满足条件的区间个数
- 判断区间 [L, R] 的情况，满足情况1，则sum++; R++。满足情况2， L++。满足情况3，结束计算。
- R每次加1，都要给numb数组中对应的数出现次数+1。当是一个新数时，要使numbR++；
- L每次减1，都要给numb数组中对应的数出现次数-1。当减为0时，要使numbL++
对于情况1，因为L不变时，后面的所有R都满足条件，所以可以修改为sum+=n-R+1； L++。
时间复杂度O(n^2) 修改之前最差为O(n^2)
空间复杂度O(2*n) numb数组的空间
看完之后是不是有了想法了呢，快来练练手吧>>查看题目：破译密码
