29. 和为 k 的子数组
题目链接：
题目描述：
题目示例：
解法（前缀和 + 哈希表）
算法思路
设 i 为数组中的任意位置，用 sum[i] 表示 [0, i] 区间内所有元素的和。要找出有多少个以 i 结尾且和为 k 的子数组，本质上就是寻找起始位置 x，使得 [x, i] 区间的和等于 k。
根据前缀和定义，[x, i] 的和可以表示为 sum[i] - sum[x-1]。若该值等于 k，则 sum[x-1] 必然等于 sum[i] - k。因此问题转化为：在遍历到 i 时，统计之前出现过多少次前缀和为 sum[i] - k。
我们不需要显式维护一个前缀和数组，只需利用哈希表记录当前前缀和出现的次数即可。一边计算当前位置的前缀和，一边查询并更新结果。
C++ 算法代码
class Solution {
public:
int subarraySum {
unordered_map<, > hash;
hash[] = ;
sum = , ret = ;
( x : nums) {
sum += x;
(hash.(sum - k)) ret += hash[sum - k];
hash[sum]++;
}
ret;
}
};
