hash

和为K的子数组

求数组中和为K的连续子数组。前缀和将问题转换为类似于两数之和的问题，再使用哈希。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // map of <sum, cnt>
        map<int, int> m;
        m[0] = 1;
        int sum = 0, ans = 0;
        for(int i = 0; i < nums.size(); i++){
            // cumsum
            sum += nums[i];
            // check answer
            if (m.count(sum - k)) ans += m[sum-k];
            // update map
            if (m.count(sum)) m[sum]++;
            else m[sum] = 1;
        }
        return ans;
    }
};