Subarray Sums II

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

Example:

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

Approach

Java

import java.util.HashMap;

public class SubArraySumII {
    public static void main(String[] args) {
        long n = 5, m = 7;

        long[] arr = { 2, -1, 3, 5, -2 };

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

    }

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

        long ans = 0;
        long cur = 0;
        HashMap<Long, Long> mp = new HashMap<Long, Long>();

        mp.put(cur, mp.getOrDefault(cur, (long) 0) + 1);

        for (int i = 0; i < n; i++) {
            long x = arr[i];
            cur += x;
            ans += mp.getOrDefault(cur - m, (long) 0);
            mp.put(cur, mp.getOrDefault(cur, (long) 0) + 1);
        }
        return ans;
    }

}

C++

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

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

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

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

    vector<long long> arr = {2, -1, 3, 5, -2};

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

    return 0;
}