题解 | #小红统计区间(easy)#
小红统计区间(easy)
https://www.nowcoder.com/practice/96e8db05848142808e69d04d604f2dd8
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是当前窗口;然后可以直接开始下一个窗口起点;