子串数量

[编程题]子串数量

热度指数：114 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个数组a[0],a[1],a[2],a[3]....a[n]。请问中间加和等于k的连续子串有多少个？

输入描述:

第一行输入两个整数n,k。n代表数组长度，k代表所求子串的和。0 < k < 10000000, 0 < n <= 100000;
第二行为n个整数,0 <=a[i] <= 100000;

输出描述:

输出一个整数代表等于k的连续子串的个数。

示例1

输入

5 4
1 2 3 1 2

输出

算法知识视频讲解

ZJYang

滑动窗口

def solu():
    try:
        n,k = input().split(' ')
    except:
        return False
    n,k = int(n),int(k)
    nums = input().split(' ')
    nums = [int(_) for _ in nums]
    
    r,l,c,res = 0,0,0,0
    while l<n:
        while c<k and l<n:
            c +=nums[l]
            l+=1
        while c==k and l<n:
            res +=1
            c +=nums[l]
            l +=1
        while c>k and r<l:
            c -= nums[r]
            r +=1
        while c==k and r<l:
            res +=1
            c -=nums[r]
            r +=1
    print(res)
    return True

if __name__=="__main__":
    while solu():
        pass

发表于 2021-08-05 02:46:11 回复(0)