一、题目解析
题目如下->:
这道题的问题是，找到目标值为k的所有连续子串个数，因此最简单最容易想到的就是枚举
两个指针枚举起来确实可以解决，但是时间复杂度极大，达到了O(n^2)的级别
因此这不是我们想要的
二、解题思路
2.1 直接的前缀和可行吗?
既然暴力枚举时间复杂度极大，我们可以思考一下更好地方法，用前缀和吗?
想象一下，如果我们要用前缀和，需要把从每个不同开头的元素的前缀和全部遍历一遍
类似数组[1,2,3]，我们需要4个前缀和才能全部搞完，[1],[1,2],[1,2,3],[2,3]
这跟暴力解法也没什么区别了，根本就是枚举！
2.2 反面思考
因此，我们不能从常规的想法进行
所以我们要思考一下反面，既然要找到目标值为k的子串个数，我们可以找与k相反的，什么意思?
请看->:
我们这里用dp[i]来表示整个数组的和，(整个数组的前缀和) 因此->:
如果一个数组存在k，那么每一个k一定存在一个对应的dp[i] - k
所以我们的目标可以转变成，找到有多少个dp[i] - k
2.3 怎么发现的?(思路转换)
我们观看一个数组[3,4,7,2,-3,1,4,2]，k = 7这个数组
可以发现，只要始终控制一段范围的数组那么只要k出现，必定会有与之对应的dp[i] - k
所以我们核心的目的变为: 找到dp[i] - k
因此我们需要做到的是控制数组，将数组分成一段一段的数组
但这里的分并不是拆分，而是控制数组的前缀和，始终让 ‘k’ 这一段范围为到数组最后一个元素的这一段，这里可能说的不太清楚，就是下图中的k这一段，始终保持到数组末尾的范围
k我们无法去控制，但是我们可以控制dp[i] ，这里的dp[i]不就是每一段数组的前缀和吗！
而dp[i]-k为我们要寻找的目标，只要能找到 dp[i]-k 就是找到了k
这里举个例子
数组 [3,4,7,2,-3,1,4,2] k = 7
数组段 dp[i] dp[i-k] 哈希表插入 哈希表次数 [3] 3 -4 hash[3] 1 [3,4] 7 0 hash[7] 1 [3,4,7] 14 7 hash[14] 1 在[3,4]中，dp[i-k] = 0
查找hash[0]出现的次数（特殊处理），因此我们需要计数
在[3,4,7]中，dp[i-k] = 7
查找hash[7]出现的次数（前面插入过）因此我们需要计数
三、细节处理 (先看代码)
1. k出现在中间怎么办?
如果k出现在中间，那么说明之前一定有过此图的情况
那么也就是更新过结果，无需考虑
2. 为什么不用前缀和?
可以用，但是没必要，用一个变量sum即可
3. 如果dp[i] = k怎么办?
如果dp[i] = k,那么dp[i] - k就等于0，说明此时就是一个目标子串，因此需要计数
但是我们的hash[0]没有数，所以需要手动设置hash[0] = 1
4.为什么子串出现次数要加hash[x]出现的次数，而不是单纯的让子串出现次数+1?
可以思考这样一个例子->:
数组:[1,-1,1,1,1] k = 2
当我们的数组段为[1,-1,1,1]时，会发现出现了两个k，分别是[1,-1,1,1]和[1,1]
此时的hash[x]为hash[sum-k] = hash[0]
那么我们要找的就是hash[0],而之前的[1,-1]使hash[0]为2了
因此如果只让次数+1会漏掉一个，因此只能加hash[x]出现的次数
5.为什么这样做是对的?
当整个数组都遍历完，说明所有 子串(k) 的情况都包含了进去，答案也就对了
6.如果k在左边，dp[i]-k 在右边怎么办?
如果k在左边，dp[i]-k在右边，那么一定找不到dp[i]-k,因为dp[i]-k在哈希表中找不到啊，哈希表存储的是前缀和，k在左边就说明dp[i]-k一定不是前缀和了，所以绝对找不到，因此不必担心结果更新冗余的问题
四、代码实现
class Solution { public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> hash;int sum = 0,ret = 0;hash[0] = 1;for(auto& e: nums){sum+=e;if(hash.count(sum-k))ret+=hash[sum-k];hash[sum]++;}return ret;} };
