subarray-sum-equals-k(Leetcode.5

题目链接Leetcoee.560
题目要求是从数组中找出有多少个子数组的和等于k。
每个人都能想到暴力求解的办法，明显O(N^2)的复杂度会TLE。想了很久我还是没有思路，就去看了别人的解法，这个题的解法其实很单一，网上那么多版本也是有统一的核心。但是这个核心并不是很好理解，比如我，两眼瞪着代码看了好久都不是很明白，最后用个例子手动跑了一遍程序才理解其中的原因。所以在此记录下来。
以题目中默认的testcase为例：

nums = [1,1,1];
k = 2;
// 变量初始化
int cum = 0; // cumulated sum
map<int, int> rec; // prefix sum recorder
int cnt = 0; 
rec[0]++;

程序执行过程中累计计算从0到i的数组元素的和，放在cum变量中，每个cum对应的值都会在map型变量rec中有个计数，这样可以避免多次遍历数组，这也是该解法的重要步骤。cnt记录的是需要返回的结果。
程序的核心循环代码如下：

for(int i = 0; i < nums.size(); i++) {
    cum += nums[i];
    cnt += rec[cum-k];
    rec[cum]++;
}

执行过程中变量的变化如下

nums       1       1        1
sum         1       2        2
rec        (1,1)  (2,1)  (3,1)
cnt           0       0        1

for循环里比较晦涩的一句就是cnt += rec[cum-k]，下面详细解释一下。
令sum[i, j]为数组中下标i+1到j的子数组的元素的和的值，pre_sum(i)为数组中下标0到i的子数组的元素的和的值，则sum[i,j]=pre_sum(j)-pre_sum(i)。则满足条件的子数组的sum[i, j] = k，即 k=pre_sum(j) - pre_sum(i)，翻译成代码就是

pre_sum(j) - k= pre_sum(i)

代码中rec[cum-k]则是记录了pre_sum(i)的个数，很明显通过语句rec[cum]++记录pre_sum(i)出现的次数，以此达到cnt计数的目的。
这下算是明白了这个题目的解法。全部代码如下（参考leetcode discuss）

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int cum = 0; 
    map<int, int> rec; // prefix sum recorder
    int cnt = 0; 
    rec[0]++; 
    for(int i = 0; i < nums.size(); i++) {
        cum += nums[i];
        cnt += rec[cum-k];
        rec[cum]++;
    }
    return cnt;
    }
}