首先想到枚举每个区间，发现2次方的复杂度会超时，然后就不会了。。。
解法：前缀和+hash
[i,j]的区间和为sums[j]-sums[i-1] ==k，转化为：sums[i-1] = sums[j] - k。
因此：遍历到j时，看一下前面有多少下标的sums[]值为 sums[j] - k，就是以j结尾和为k有多少个。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int ans = 0, n = nums.size();
vector<int> sums(n);
unordered_map<int, int> ump;
sums[0] = nums[0];
if (sums[0] == k) ans++;
ump[sums[0]]++;
ump[0]++; //
for (int i = 1; i < n; ++i) {
sums[i] = sums[i - 1] + nums[i];
ans += (ump.count(sums[i] - k)) ? ump[sums[i] - k] : 0;
ump[sums[i]]++;
}
return ans;
}
};
易错点：hash初始化应该把{0, 1}放进去。
上面代码的优化：
可以发现，j之前的前缀和都记录在了ump中，前面的sums并没有什么用，所以sums数组用一个变量sums来取代即可。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int ans = 0, n = nums.size(), sums = nums[0];
unordered_map<int, int> ump;
if (sums == k) ans++;
ump[sums]++;
ump[0]++;
for (int i = 1; i < n; ++i) {
sums = sums + nums[i];
ans += (ump.count(sums - k)) ? ump[sums - k] : 0;
ump[sums]++;
}
return ans;
}
};