#include <unordered_map>

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int res = 0;
        // partial sum -> how many times we had this time so far
        unordered_map<int, int> m;
        int sum = 0;
        for(auto i = nums.cbegin(); i != nums.cend(); i++) {
            sum += *i;
            if(sum == k) {
                res++;
            }
            // partial sums before now, mathching with sum into k
            auto match = m.find(sum - k);
            if(match != m.end()) {
                res += match->second;
            }
            // then insert current partial sum into the map
            auto cur = m.find(sum);
            if(cur != m.end()) {
                cur->second++;
            } else {
                m[sum] = 1;
            }
        }
        return res;
    }
};