# C++ prefix sum + map

• ``````class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int cum=0; // cumulated sum
map<int,int> rec; // prefix sum recorder
int cnt = 0; // number of found subarray
rec[0]++; // to take into account those subarrays that begin with index 0
for(int i=0;i<nums.size();i++){
cum += nums[i];
cnt += rec[cum-k];
rec[cum]++;
}
return cnt;
}
};
``````

• Hey, so I don't really know what I'm doing, but when you write:

`````` rec[0]++; // to take into account those subarrays that begin with index 0
``````

Doesn't that go against the test case in the image below.

In case the image doesn't come through...

The test case is nums = [1] and k = 0.

Apparently the test case requires that the output is 0.

Thus the empty set doesn't count here.

• @reedjosh
I don't know if I understand your question.
My output of this case is 0.
Your question might be why it is correct.

My whole idea is in each step (step i), I add to my result the number of prefix arrays (of the current prefix[0..i]) whose sum is`cum-target`, as is shown below:

``````Input: nums = [0;1;2;3;4......n-1], target = k
In Step i: current prefix array [0;1;2;......i]
``````

We want to add for each step, the number of prefix arrays `a = [0;1......j]`such that:
`sum([0;1;2......j]) = sum([0;1......i]) - k` and `j <i`

Here `rec[0]++` is saying that we should not forget that `[0;1......i]`is also potentially a subarray that satisfy the conditions.

I hope this can help.

• @70664914

No, I see why it works in your case. I had a different control structure than yours, but I was working on the same idea. I was sort of fudging the bounds instead of logically creating them. I need to be better about that.

``````int subarraySum(vector<int>& nums, int k){
map<int, int> a_map;
int running_sum = 0, needed = 0, sub_arrs = 0;

for (int i = 0; i <= nums.size(); i++){
needed = running_sum - k; // Amount to remove from running sum to equal k.
sub_arrs += a_map[needed]; // Add ways needed can be made in previous arr.
a_map[running_sum]++; // Add the running sum to the map.
running_sum += nums[i]; // Manage running sum.
}

return sub_arrs;
}
``````

I should have worked through the code better before asking you that question. My version adds 0 by checking for previous sums first. I make up for this by doing a <= in the for loop.

Clearly I would have a problem with nums[i] if it weren't a vector that allows this.

• @70664914 if rec records the number of subarrays with sum as its key,how can rec[0]=1 be justified?Won't it mean then that there exists a subarray with sum=0?
Correct me wherever you think I'm wrong.

• Very wise solution, now I know Prefix Sum.

• @70664914 Hi,
A minor addition. Using unordered_map will improve runtime

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.