前缀和+哈希：和为K的子数组

题目描述：
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。

OJ链接

一开始看到这道算法题时，我首先想到的是前缀和+滑窗来解决，但是在实际构写滑窗循环时，发现很难兼顾到各种情况，因为这道算法题的数据范围是正负交替的。

使用滑动窗口，本质上是将O(n ^ 2)的时间复杂度优化成为O(n)。一般而言，滑动窗口的做法都是在暴力枚举的基础上优化而来的——通过一定的逻辑分析，舍弃掉大量无意义的枚举情况，进而优化时间复杂度。

但是，在这道题目，这样的数据范围之下，是没有办法用滑窗进行解决的，因为数据取值正负情况的不同，会带来优化逻辑的不同，而且目标和 K 也是可以正负取值的(想清楚这一点很重要)。

所以，在确认滑动窗口无法解决此道题目后，接下来介绍两种算法。

暴力枚举：

我们可以先维护一个前缀和数组，这个前缀和数组使得原数组中任意一个子数组的和都能在O(1)的时间复杂度下求出，然后在暴力枚举每一个子数组。

暴力枚举每一个子数组时，通常按照一定的规律：以某个数为结尾，或者以某个数为开始。这两种枚举方案都可以确保枚举到所有的情况。

以下是提供的参考代码，其中枚举时选择以某个数为结尾这种方案。

    int subarraySum(vector<int>& nums, int k) {int sz = nums.size();vector<int> dp(sz + 1);for(int i = 1;i <= sz;i++)dp[i] = dp[i - 1] + nums[i - 1];int count = 0;for(int i = 1;i <= sz;i++)for(int j = 1;j <= i;j++)if(dp[i] - dp[j - 1] == k)count++;return count;}

非暴力枚举：前缀和+哈希

实际上，这道题目不需要用暴力枚举的算法。

我们来分析以下这道题目。题目要求我们找到一个和为k的非空子数组，首先这个非空子数组一定是以数组中的某个数为结尾的，也就是说，我们实际上要做的工作就是——对于原数组中的任意一个数，我们想要找到是否有一个和为k的子数组以之为结尾，就是在该数之前再找到一个数，使这两数之间的数和为k——再进一步转换，要使得这两数之间的和为k,既存在子数组在原数组中左半部分的数和为sum - k(sum是该子数组右边界所对应的前缀和)。

这样转换后，我们去找原数组中以某个数为结尾的和为k的子数组是否存在时，实质上就是去找该数之前所有数对应的前缀和中，有无等于sum - k，如果有，又存在几个(sum是该数所对应的前缀和).

我们当然可以遍历取查找sum - k，但是这样本质也是暴力枚举，想要在O(1)的时间复杂度内查找一个数是否存在，查找一个数存在几次，我们可以利用哈希表的结构。在这个哈希表中，前缀和为key值，该前缀和出现的次数则为value值。

另外，在这种做法中，不需要提前维护好一个前缀和数组，因为找以某数为结尾的子数组，只需要查找该数之前的前缀和是否存在sum - k,既当前状态只依赖于之前的状态，有点类似于动态规划问题中的滚动数组优化，所以，我们可以一边迭代前缀和，以便维护好前缀和的哈希结构。

具体代码如下所示(在代码示例中，是以某个数为结尾进行构建的，若更改为以某个数为开始，也是可行的)

    int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> hash;hash[0] = 1;//默认0的个数为1int count = 0;int sum = 0;for(auto& e : nums){sum += e;if(hash.count(sum - k))count += hash[sum - k];hash[sum]++;}return count;}