Find number of subarrays with given sum (positive numbers) [Sliding window]

Given an array of positive 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 = 0, start = 0
3.  for i = 0 to n-1
4.    currSum = currSum + A[i]
5.    while currSum > k && start<= i
6.      currSum = currSum - A[start]
7.      start++
8.    if (currSum == k) {
9.      num++
10. return num 

Code Implementation

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


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

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

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

    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