题解 | #连续子区间和#

双指针 or 滑动窗口

i：区间左指针； j：区间右指针。两个指针都分别向右移动

• 右移 j (增大窗口)：

当前窗口内的子数组和(s) += nums[j]

• 在 j 位置固定的情况下，不断右移 i (缩小窗口)：

! 由于数组元素都是正整数，因此大区间的和一定大于小区间的和。

因此，若当前区间[i, j]满足之和(s) >=x，则区间[i, k]一定满足之和 >=x（j < k < n）因此，每次cnt += n - j。

直至窗口内的的子数组和(s)< x，i 停止移动。

n, x = list(map(int, input().split()))
nums = list(map(int, input().split()))

i, j, s, cnt = 0, 0, 0, 0
while j < n:
    s += nums[j]
    while i <= j and s >= x: 
        cnt += n - j # ！！！
        # 缩小窗口
        s -= nums[i]
        i += 1
    # 增大窗口
    j += 1

print(cnt)