在线编程介绍
阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding
本文为大家介绍其中的第57题：超级区间 的题目解析，具体如下：
题目描述
题目等级：中等
知识点：二分查找、尺取法
查看题目：超级区间 Tom现在有一个长度为n的数组，Jerry给Tom定义了一种超级区间，如果区间[l,r]满足(a[l]+…+a[r])>=k,则区间[l,r]被称为超级区间，现在Jerry想让Tom告诉他数组中有多少个超级区间。
输入整数n,整数k(1<=n,k<=100000)，和一个大小为n的数组，数组的每个元素的大小都在[1,1000]之间。
输出输入数组的超级区间的个数。
示例1
输入：
3
5
[2,3,5]
输出：
4
注意
样例满足条件的超级区间为
[1,2],[2,3],[1,3],[3,3]。
解题思路：尺取法
使用 尺取法 对搜索空间进行遍历。
设当前区间为[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]都不满足超级区间的定义。
计算过程
- 初始L = R = 0；sum = 0; 用来计算满足条件的区间个数
- 判断区间 [L, R] 的情况，满足情况1，则sum++; R++。满足情况2， L++。满足情况3，结束计算。
对于情况1，因为L不变时，后面的所有R都满足条件，所以可以修改为sum+=n-R+1； L++。
时间复杂度O(n^2) 修改之前最差为O(n^2)
空间复杂度O(1) 记录当前区间数组元素的和
看完之后是不是有了想法了呢，快来练练手吧>>查看题目：超级区间