连续子区间和

[编程题]连续子区间和

热度指数：3979 时间限制：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

输出

说明

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

2 = 2

4 = 4

7 = 7

2 + 4 = 6

4 + 7 = 11

2 + 4 + 7 = 13

其中有4个和大于等于6，所以答案等于4。

算法知识视频讲解

Python

牛客406598143号

def func():
c,x = map(int, input().strip().split())
lis_array = [int(x)for x in input().split()]
sum_num = 0
count_num = 0
j = 0
for i in range(len(lis_array)):
if sum_num < x:
sum_num += lis_array[i]
while j < c and sum_num >= x:
count_num += c - i
sum_num -= lis_array[j]
j += 1
print(count_num)
if __name__=="__main__":
func()

发表于 2022-05-10 21:25:37 回复(1)

Python

ElonB

""""
正整数数组，sum(a[i:j])>x，则sum(a[i:j+k])都大于x，j+k<=n，k为满足条件的个数
使用滑动窗口优化
"""

if __name__ == "__main__":
    n, x = map(int, input().strip().split())
    a = list(map(int, input().strip().split()))
    i, j, t_sum, ans = 0, 0, 0, 0
    while True:
        while j < n and t_sum < x:
            t_sum += a[j]
            j += 1
        if j == n and t_sum < x:
            break
        ans += n - j + 1
        t_sum -= a[i]
        i += 1
    print(ans)

发表于 2019-07-17 11:16:33 回复(0)