leetcode-560. 和为 K 的子数组
题目描述
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2 输出：2
示例 2：
输入：nums = [1,2,3], k = 3 输出：2
思路
前缀和
参考：算法面试实录-和为 k 的子数组_哔哩哔哩_bilibili 这个视频讲的很清楚
1）变量pre用来记录前缀的累加和
2）字典记录：当前位置累加和出现的次数。PS：需初始化{0:1}
3）遍历数组，如果前缀和-k在字典中，count+=字典中的次数
class Solution(object):
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
count = 0
pre = 0
pre_dict = {0:1}
for num in nums:
pre += num
if pre - k in pre_dict:
count += pre_dict[pre-k]
if pre in pre_dict:
pre_dict[pre] += 1
else:
pre_dict[pre] = 1
return count
if __name__ == '__main__':
s=Solution()
nums = [1,2,3]
k = 3
print(s.subarraySum(nums, k))