四时可爱唯春日
一事能狂便少年
C++，暴力和，或者hash，前者不需要额外空间，后者需要额外空间。
暴力和解法
有一种很简单的方法，就是将nums数组变成和数组，nums[i]表示的是nums[0]到nums[i]的累加和。通过两层循环，记录nums[j] - nums[i - 1]，就可以得到所有的和，然后找出等于K的和就行了。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
sums.resize(nums.size());
for (int i = 0; i < nums.size(); i++) {
if (i >= 1)
nums[i] = nums[i-1] + nums[i];
}
int ans = 0;
for (int i = 0; i < nums.size(); i++) {
for (int j = i; j < nums.size(); j++) {
long sum = 0;
if (i > 0)
sum = nums[j] - nums[i - 1];
else sum = nums[j] - 0;
if (sum == k) ans++;
}
}
return ans;
}
};
Hash解法
从上述暴力和解法出发，现在不记录出现某个位置的累加和，而是用hash表记录所有累加和出现过的次数。题目中需要求的是子列和，所以需要的是中间某个序列的和。中间某个序列的和，可以由前后两个累加和的差得到，实际上我们只要判断这个差是不是等于K就可以了。
具体思路：
- 遍历数组得到累加和的hash，键是累加和，值是累加和出现的次数
- 遍历hash表，可以得到任一累加和sum，sum减去K，如果得到的数也在hash表中的话，说明构成了一个满足题意的子序列，也就是满足子列和是K
有点绕，但联系之前的暴力累加和解法就比较好理解了，相当于利用额外空间记录了之前舍弃的累加和信息。
需要注意的是，hash[0] == 1。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> hash;
int sum = 0, ans = 0;
hash[0] = 1;
for (const int &it : nums) {
sum += it;
ans += hash[sum - k];
hash[sum]++;
}
return ans;
}
};
