# Find number of subarrays with given sum (with Negative numbers) – LeetCode Solution [Medium]

In the previous post, we discussed about finding the total number of continuous subarrays of a given array (of non-negative numbers) whose sum equals to k.
In this post we’ll include negative numbers in the given array arr.

Problem

Given an array of integers arr[] and an integer k, return the total number of subarrays whose sum equals to k. A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: arr = [-1, -1, 1], k = 0
Output: 1
Explanation: arr[1, 2] ie -1 + 1 = 0, hence one subarray.
###### Find number of subarrays with given sum solution

Approach

The idea is, if the sum of consecutive array elements from arr[i] to arr[i+k] is same, then the sum of elements from arr[i] to arr[i+k] = 0. Similarly, if sum of elements between two indices i and j is such that: sum[i]-sum[j] = k, then the sum of elements between i and j indices is k.

We’ll use a hashmap (map), with key as the sum of the array elements upto current index (i) and value as the number of subarrays with the given key (sum).

Pseudocode

1. Initialize: sum = 0, solution = 0, map[0] = 1
2. N = A.size()
3. for i = 0 to N-1
4.   sum += A[i]    //sum till ith element
5    if (map.find(sum-k) != map.end()) //finding sum-k upto i
6.     solution += map[sum-k]
7.   map[sum] += 1
8. return solution

Code Implementation

//
//  main.cpp
//  Subarray with sum
//
//  Created by Himanshu on 18/09/21.
//

#include <iostream>
#include <climits>
#include <map>
using namespace std;
const int N = 7;

int subarraySum(int A[], int k) {
map<int, int > hmap;
int sum = 0, sol = 0;

hmap[0] = 1;

for (int i=0; i<N; i++) {
sum = sum + A[i];

if (hmap.find(sum-k) != hmap.end()) {
sol += hmap[sum-k];
}

hmap[sum] += 1;
}

return sol;
}

int main() {
int A[N] = {5, 2, 4, -6, -1, -1, 1};
int k = 6;

cout<<"Number of subarray with sum "<<k<<": "<<subarraySum(A, k)<<endl;

k = 0;
cout<<"Number of subarray with sum "<<k<<": "<<subarraySum(A, k)<<endl;

return 0;
}


Output

Number of subarray with sum 6: 1
Number of subarray with sum 0: 2

Here’s a working example: Ideone