这道题的正解是 树状数组,但是我们用朴素解法 枚举所有子数组 也能在考试时拿到一定的分数。
题意:给定长度为 n 的数组 papers,以及闭区间 [left,right],统计有多少个连续子数组,其元素之和落在 [left,right] 内。
朴素做法:
今天,小明的数学老师带来了一叠数字卡牌,每张卡牌上标有数字,有正有负也有零。老师打乱了卡牌顺序,并将牌面展示出来。接着老师在黑板上写下了一个闭区间范围 [left, right]。
老师对小明说:“你可以从这叠卡牌中任意抽取一叠,起始位置不限,抽取的张数不限,但是有个要求,你抽取出的卡牌,牌面加起来的和需要落在黑板上的区间范围内。小明,你算算看,一共能有几种抽取方法?”
小明听完,眼冒金星。你能帮助小明写个程序,算出有几种方法吗?
n(1 < n <= 10000)papers[](-255 <= papers[i] <= 255),共 n 个整数left 与右值 right(-2550000 <= left <= right <= 2550000)输入:
4
1 -1 1 -1
0 0
输出:
4
解释:
共有4张纸牌,牌面数字为1,-1,1,-1,方法为取第1张到2张,取第2张到第3张,取第3张到4张,取第1到4张,共4种
输入:
3
-3 4 -2
-3 2
输出:
5
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册