力扣hot100菜鸟版 题号560

题目

废话少说，直接看题目，首先理解一下题意，子数组的要求是数组中元素的连续非空序列。

在示例1中，就是下标0，1和下标1，2这两个子数组。

然后是示例2，下标0，1是显然的，我看了好久都没找到第二个在哪，问了ai才知道下标2就是一个子数组，不知道有没有和我一样的人（哭笑不得）

思路

帮大家试过二重循坏暴力解法了，过不去

熟悉的人肯定知道这题考察的是前缀和，但是别急，先让我们看看前缀和的基本原理。

对一个元素序列：3，4，56，6，7，6，7。

当我们要求下标2到下标4闭区间的和时，我们应该怎么做？

注意到公式，下标0到下标4闭区间的和减去从下标0到下标1闭区间的和，即为所求。这就是前缀和的基本原理，线性遍历得到前缀和，通过不同下标的前缀和相减得到任意区间的和，符合空间换时间的思想。前缀和基本公式：

下标闭区间L，R的区间和=R的前缀和减去L-1的前缀和

（看了一些视频，感觉前缀和的理解有多种，有些前缀和好像是开区间的，整体思路是一样的，这里我采用闭区间的思路）

代码

class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map <int,int> map;//key为前缀和，value为这个前缀和出现的次数 map[0]=1;//这个要特别注意，下文有解释 int pre_sum=0; int res=0; for(int i=0;i<nums.size();i++){ pre_sum+=nums[i]; if(map.find(pre_sum-k)!=map.end()) res+=map[pre_sum-k]; map[pre_sum]++; } return res; } };

（这个代码里面的注释咋改颜色啊，根本看不清啊）

考虑如下序列：1。给定的k也为1。

按照代码逻辑，此时寻找map中是否存在key,使其等于pre_sum-k即1-1即0，如果代码中没有设置

map[0]=1的话，就漏解了。接下来要思考为啥有这个特殊情况，难道上面的思路有问题？

根据公式，想要计算下标0到下标0的闭区间的和，需要用下标0的前缀和减去“下标-1”的前缀和，

所以咱们的思路没问题。

碎碎念

最近懈怠了十几天，罪过罪过，明天继续努力！