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.

LeetCode Problem Link

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