20453: 和为k的子数组个数

http://cs101.openjudge.cn/practice/20453/

给定一组整数数字和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

输入

第一行:由空格区分的一组数字 第二行:整数k

输出

一个整数，代表多少子数组等于k

样例输入

1 1 1
2

样例输出

2

提示

有两组1 1 和为2

通过使用一个哈希表来存储前缀和的频率来解决。我们遍历输入的数组，每次迭代时，我们都会更新当前的前缀和。然后，我们检查哈希表中是否存在当前前缀和减去目标值k的条目。如果存在，我们就将其值添加到结果中。最后，我们将当前的前缀和添加到哈希表中。

def subarray_sum(nums, k):
    count = 0
    sums = 0
    d = dict()
    d[0] = 1

    for i in range(len(nums)):
        sums += nums[i]
        count += d.get(sums - k, 0)
        d[sums] = d.get(sums, 0) + 1

    return count

nums = list(map(int, input().split()))
k = int(input().strip())
print(subarray_sum(nums, k))