题目描述

给你一个整数数组 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 = 0pre = 0pre_dict = {0:1}for num in nums:pre += numif pre - k in pre_dict:count += pre_dict[pre-k]if pre in pre_dict:pre_dict[pre] += 1else:pre_dict[pre] = 1return countif __name__ == '__main__':s=Solution()nums = [1,2,3]k = 3print(s.subarraySum(nums, k))