八股文Note1

LeetCode #560.和为k的子数组

题目描述：

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

子数组是数组中元素的连续非空序列。

思路：

1. 用Python写的，上来就暴力解法，果然时间超时，放弃。

2. 用了前缀和数组求数组范围之和，时间超时，换C++，还是超时，放弃。

3. 一番挣扎，上网搜索，恍然大悟，做个笔记，记录解法。

解法：

用一个字典记录遍历的所有前缀和及其出现次数，假设当前前缀和为A，如果存在到A的子数组的和为k的话，那么必定存在前缀和为A-k，数量为字典中记录的值。

代码如下：

如侵删，欢迎评论指正。