题解 | #小红统计区间(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是当前窗口;然后可以直接开始下一个窗口起点;

全部评论

相关推荐

Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务