算法笔试模拟题精解之“超级区间”-阿里云开发者社区

开发者社区> 算法编程> 正文
登录阅读全文

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

简介: 使用 尺取法 对搜索空间进行遍历。设当前区间为[L, R]。初始L = R = 0;使用尺取法需要判断什么时候调整L和R。

在线编程介绍

阿里云开发者社区在线编程产品,针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等,界面整洁明了,操作简单,为用户营造专心答题的学习环境。点击链接开始体验: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) 记录当前区间数组元素的和

看完之后是不是有了想法了呢,快来练练手吧>>查看题目:超级区间

image.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
最新文章
相关文章
链接