n, k = map(int, input().split())
nums = list(map(int, input().split()))
left = right = 0
sum_ = 0
ans = 0
while left < n and right <= n:
if sum_ < k:
if right == n:
break
sum_ += nums[right]
right += 1
else:
# print(f'right:{right}, left:{left}')
ans += n - right + 1
sum_ -= nums[left]
left += 1
print(ans)
因为都是正整数,所以利用滑动窗口,窗口增加就是区间和变大,反之区间和减小;
left的含义还可以是窗口起点,每次区间和超过阈值的时候,就可以直接计算剩下的可行窗口数量为n-right,+1是当前窗口;然后可以直接开始下一个窗口起点;


京公网安备 11010502036488号