# 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, 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, 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