LeetCode 560. Subarray Sum Equals K

https://leetcode.com/problems/subarray-sum-equals-k/description/
O(N^2)的方法想必所有人都会，这里有个用到prefix sum的O(N)方法。
试想一下，如果当前检查到end位置且目前所有项的和为sum，如果有那么一个(start, end)子序列的和为k，那么肯定有一个(0, start-1)的序列它的和是sum – k.

[a, b, c] \___k__/
[a, b, c, d, e, f]
/sum - k\

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> cum_sums;   // <cum_sum, count>
        cum_sums[0] = 1;
        int sum = 0;
        int count = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            sum += nums[i];
            if (cum_sums.count(sum - k) > 0)
                count += cum_sums[sum - k];
            cum_sums[sum]++;
        }
        return count;
    }
};