算法笔试模拟题精解之“超级区间”

在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：

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]都不满足超级区间的定义。

计算过程

1. 初始L = R = 0；sum = 0; 用来计算满足条件的区间个数

2. 判断区间 [L, R] 的情况，满足情况1，则sum++; R++。满足情况2， L++。满足情况3，结束计算。

   对于情况1，因为L不变时，后面的所有R都满足条件，所以可以修改为sum+=n-R+1； L++。

时间复杂度O(n^2) 修改之前最差为O(n^2)

空间复杂度O(1) 记录当前区间数组元素的和

看完之后是不是有了想法了呢，快来练练手吧>>