算法（十）--前缀和

前缀和

如何定义前缀和呢？

所以有s[i+1] = s[i] + nums[i]

下标从i到j-1的非空连续数组的元素和等于k，说明s[j] - s[i] = k

和为k的子数组

将上面的式子转换一下，得到s[i] = s[j] - k；这表示元素和为k的子数组的个数。然后在遍历数组的过程中用哈希表记录前缀和出现的次数，每遍历一个元素，就查看是否存在前缀和为pre - k的，如果存在就在ans加上哈希表中pre - k的个数。

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> map;
    int ans = 0, pre = 0;
    map[0] = 1;
    for (auto num : nums) {
        pre += num;
        if (map.count(pre - k) == 1) {
            ans++;
        }
        map[pre]++;
    }
    return ans;
}