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[cumk];
rec[cum]++;
}
return cnt;
}
};
C++ prefix sum + map


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
cumtarget
, as is shown below:Input: nums = [0;1;2;3;4......n1], 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
andj <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.

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.
Thanks for your response though!

@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.

