Subarray Sums I

Given an array of n positive integers, your task is to count the number of subarrays having sum x.

Example:

Input: n = 5, m = 7, arr = {2, 4, 1, 2, 7}
Output: 3

Approach

Java

import java.util.HashMap;

public class SubArraySumI {
    public static void main(String[] args) {

        long n = 5, m = 7;

        long[] arr = { 2, 4, 1, 2, 7 };

        System.out.println(subArraySumI(n, m, arr));

    }

    static long subArraySumI(long n, long m, long[] arr) {

        HashMap<Long, Long> mp = new HashMap<Long, Long>();
        mp.put((long) 0, mp.getOrDefault(0, (long) 0) + 1);
        long sum = 0;
        long ans = 0;
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            mp.put(sum, mp.getOrDefault(sum, (long) 0) + 1);
            ans += mp.getOrDefault(sum - m, (long) 0);
        }
        return ans;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

long long subArraySumI(long long n, long long m,
                       vector<long long> &arr)
{

    map<long long, long long> mp;
    mp[0]++;
    long long sum = 0;
    long long ans = 0;
    for (long long i = 0; i < n; i++)
    {
        sum += arr[i];
        mp[sum]++;
        ans += mp[sum - m];
    }
    return ans;
}

int main()
{
    long long n = 5, m = 7;

    vector<long long> arr = {2, 4, 1, 2, 7};

    cout << subArraySumI(n, m, arr) << "\n";

    return 0;
}