First. Problem’s Description

Second. Problem’s Solution

  • Use a HashTable to store the pre_sum of the array, use unordered_map<sum, how_many> ump;
  • When we start, insert pair<int, int>(0, 1)into the unordered_map first, that represents even if the array is null, there is still a sub_array whose sum is 0, although the sub_array is empty.
  • Then we traverse the array, find another adder according the given kand the current array element, so we can calculate the wanted_num: auto wanted_sum = sum - k;.Then turn to unordered_map to find if wanted_sumis in unordered_map and if it exists, count += ump.find(wanted_sum)->second;

Third. Code For Problem

class Solution {
   
public:
    int subarraySum(vector<int>& nums, int k) {
   
        unordered_map<int, int> ump;    //sum, howmany
        int sum = 0;
        ump[0] = 1;
        int count = 0;
        for(int i = 0; i < nums.size(); i++){
   
            sum += nums[i];
            auto wanted_sum = sum - k;
            if(ump.find(wanted_sum) != ump.end())   count += ump[wanted_sum];
            ump[sum]++;
        }
        return count;
    }
};

Four. Processing Result