Find number of subarrays with given sum (Non-negative numbers) [Sliding window]

Given an array of non-negative integers arr and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1:

Input: arr = [1,1,1], k = 2
Output: 2

Example 2:

Input: arr = [1,2,3], k = 3
Output: 2

Find number of subarrays with given sum solution

Approach

This problem could be solved by Sliding window technique, discussed in this post.

Pseudocode

Quick Tip:
A useful tip for naming variables and methods – name of a variable should be a noun and name of a method should be a verb.

FindSubarray (A, k)
1. num = 0, n = Size[A]
2. currSum = A[0], start = 1
3. for i = 1 to (n+1)
4.   for j = start to (i-1) && currSum > k
5.     currSum = currSum - A[j]
6.   start = j
7.   if (currSum == k) {
8.     num++
9.   if (i < n)
10.    currSum += A[i]
11. return num 

Code Implementation

//
//  main.cpp
//  Number of subarray with given sum
//
//  Created by Himanshu on 18/09/21.
//


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

int solve (int A[], int k) {

    int num = 0, currSum = A[0], start = 0, j;
    
    for (int i=1; i<=N; i++) {
        for (j = start; currSum > k && j < (i-1); j++) {
            currSum = currSum - A[j];
        }
        start = j;
        
        if (currSum == k) {
            num++;
        }
        
        if (i<N) {
            currSum += A[i];
        }
    }

    return num;
}
 
int main() {
    int A[N] = {5, 3, 4, 6, 8, 11, 20};
    int k = 7;
    
    cout<<"Number of subarray with sum "<<k<<": "<<solve(A, k)<<endl;
    
    k = 4;
    cout<<"Number of subarray with sum "<<k<<": "<<solve(A, k)<<endl;
    
}

Output

Number of subarray with sum 7: 1
Number of subarray with sum 4: 1

Here’s a working example: Ideone