邢台专业做网站哪家好网络营销怎么做

题目

链接:leetcode链接

思路分析（前缀和）

注意：我们前面讲过滑动窗口可以处理子数组、子串等问题，
但是在这道题目里面注意数据范围 -1000 <= nums[i] <= 1000
nums[i]可正可负，区间的和没有单调性，使用不了滑动窗口

这里带来新的解决方法
这道题目也是要求我们求一段连续区间的和，我们的前缀和算法也能帮助我们做到 [l , r] = dp[r] - dp[l - 1]

所以，我们求区间和为k，也就是，k = sum[r] - sum[l - 1]

抽象来看，存在一个区间的和为k，那么在==[0 , i - 1]==就存在一个前缀和为sum - k
我们只需要去寻找这个sum - k的前缀和即可。

思考一下，我们真的需要另外去开一个前缀和数组吗？
如果开前缀和数组的话，那也是需要遍历前缀和数组，以每一个下标为终点当sum去找sum - k，时间复杂度依旧是O(N²)，这和暴力有啥区别呢？

所以是不需要开前缀和数组的，
我们只需要sum - k的个数，为什么不使用hash表呢？
我们每次算到一个新的前缀和，去hash表中查找sum - k的个数，不就可以解决了嘛

此时的sum前缀和，采用滚动数组的方式，利用一个变量就可以统计所有的前缀和了（这里后续不会使用，所以前缀和并不用存起来，所以并不需要实质地开一个数组）

细节：
（1）我们什么时候把前缀和插入hash表
我们要在[0 , i - 1]中查找hash表，也就是要先查找，再插入，
否则就是在[0,i]中查找
在[0，i]中查找的话，如果k是0的话，就会出现bug，
比如只有一个元素1，插入hash表后
sum - k还是等于1，但是我们要找的是和为0，
在hash里面找到了1，就返回1，但是实际上是没有符合要求的子数组

（2）如果[0,i]的前缀和恰好等于k怎么办呢？
此时我们需要特殊处理，
这种情况下，sum - k等于0，此时的对应的sum - k区间不存在，这种情况要特殊处理一下，
在创建hash表的时候，额外把hash[0] = 1，来提前应对这种情况

代码

int subarraySum(vector<int>& nums, int k) {int sum = 0;int ret = 0;unordered_map<int,int> hash;hash[0]++;for(auto & e:nums){sum += e;int check = sum - k;if(hash.count(check)) ret += hash[check];hash[sum]++;}return ret;}