Description

Submission

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int n = nums.size();
        nums.insert(nums.begin(), 0);

        vector<int> presum(n+1);
        presum[0] = 0;
        for(int i = 1; i <= n ; ++i) {
            presum[i] = presum[i-1] + nums[i];
        }

        int ret = 0;
        
        for(int i = 0; i <= n; ++i) {
            int right = goal + presum[i];   // right side
            auto it = lower_bound(presum.begin() + i + 1, presum.end(), right);
            for(; it != presum.end() && *it == right; ++ret, ++it);
        }

        return ret;
    }
};