首页 > 试题广场 >

连续子区间和

[编程题]连续子区间和
  • 热度指数：4132 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解

小M给你一串含有c个正整数的数组, 想让你帮忙求出有多少个下标的连续区间, 它们的和大于等于x。


输入描述:
第一行两个整数c x（0 < c <= 1000000, 0 <= x <= 100000000)

第二行有c个正整数（每个正整数小于等于100)。


输出描述:
输出一个整数，表示所求的个数。
示例1

输入

3 6
2 4 7

输出

4

说明

对于有3个整数构成的数组而言，总共有6个下标连续的区间，他们的和分别为：

2 = 2

4 = 4

7 = 7

2 + 4 = 6

4 + 7 = 11

2 + 4 + 7 = 13

其中有4个和大于等于6，所以答案等于4。
算法知识视频讲解
开通博客
头像 BoolChen
发表于 2021-03-08 15:22:43
原理：若数组从下标0累加到i，会超过x，则从1累加到c的数字也必然超过x（数组是正整数）。故使用滑动窗口，l、r分别为左右指针，length为数组长度（c）。 r持续向右移动，直到和超过x，此时length-r就是从l开始的解的数量。 随后，将l+1，求下一个起点的解的数量。 while(lin 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 日神与酒神
发表于 2024-04-18 17:56:49
双指针 or 滑动窗口i：区间左指针； j：区间右指针。两个指针都分别向右移动右移 j (增大窗口)： 当前窗口内的子数组和(s) += nums[j]在 j 位置固定的情况下，不断右移 i (缩小窗口)： ! 由于数组元素都是正整数，因此大区间的和一定大 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客题解官
发表于 2020-06-05 18:52:50
题解： 考察点： 滑动窗口，数形结合 易错点： 在本题中数据范围为，如果使用暴力求解是行不通的，因为如果使用复杂度为的暴力，那运算次数将达到，一般来说，在时间范围内所能抗住的运算次数在 解法：滑动窗口 首先，先从下图来观察出一个很重要的结论： 对于一个全由正整数构成的序列来说，如果区间中所有元素 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 贪心 分治 数组 Momenta 穷举 2019 Java工程师
来自：Momenta2019...
上传者：小小
难度：
18条回答 17957浏览

热门推荐

通过挑战的用户

查看代码

相关试题

连续子区间和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号