C++ prefix sum + map


  • 7
    7
    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;
        }
    };
    

  • 0
    R

    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.

    alt text

    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.


  • 1
    7

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


  • 0
    R

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

    Thanks for your response though!


  • 0
    M

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


  • 0
    C

    Very wise solution, now I know Prefix Sum.


  • 1
    A

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


Log in to reply
 

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