In this post, we will make a C++ program to print the total number of subarray sums equals k. We will also code another program based on the idea of a cumulative sum.

Total Number of Subarrays whose Sum Equals k
Given an unsorted array of integers. We will find the number of continuous subarrays having a sum exactly equal to k in linear time complexity. We will use hashmap to store prefix sum.
Problem link: Leetcode
int subarraySum(vector<int>& nums, int k) {
int sum=0,ans=0;
unordered_map<int,int> mp;
mp[0] = 1; // we always have 1 sum of zero, which is sum of none.
for(int i=0;i<nums.size();i++)
{
sum+=nums[i];
// We have x prefix array to create this value. So count is added with the existing combinations
if(mp.find(sum-k)!=mp.end())
ans+=mp[sum-k];
mp[sum]++;
}
return ans;
}
C++ Program to Print Total Number of Subarrays having Sum Exactly Equal to K
In this program, we will make a program that takes an array from the user and Subarray sum(k). We will print the total number of Subarray sums equal to k.
Time complexity for finding the number of subarrays sum equals k: O( N3)
#include<iostream>
using namespace std;
int main()
{
int arr[1000], k, n, ksum, currentsum, count = 0;
cout<<"n Enter number of elements:";
cin>>n;
cout<<"n Enter array elements:";
for (int i = 0; i < n; i++)
{
cin>>arr[i];
}
cout<<"n Subarray sum equals:";
cin>>ksum;
for (int i=0; i<n; i++)
{
for(int j = i; j < n; j++)
{
currentsum=0;
for(int k = i; k <= j; k++)
{
currentsum+= arr[k];
}
if ( currentsum == ksum)
count++;
}
}
cout<<"Total no. of subarray sum equals "<<ksum<<" is ";
cout<<count;
return 0;
}
Enter the number of elements:9
Enter array elements:-4 1 3 -2 6 2 -1 -4 -7
Subarray sum equals:10
Total no. of subarray sum equals ten is 1
Video Solution
Program to Print Total number of Subarray Sum equals k using Cumulative Sum
The time complexity for finding the count of subarrays sum equals k using cumulative sum: O( N 2)
#include<iostream>
using namespace std;
int main()
{
int arr[1000], k, n, ksum, currentsum, count = 0,cumulativesum[1000]={0};
cout<<"n Enter number of elements:";
cin>>n;
cout<<"n Enter array elements:";
cin>>arr[0];
cumulativesum[0]=arr[0];
for (int i = 1; i < n; i++)
{
cin>>arr[i];
cumulativesum[i] = cumulativesum[i-1] + arr[i];
}
cout<<"n Subarray sum equals:";
cin>>ksum;
for (int i=0; i<n; i++)
{
for(int j = i; j < n; j++)
{
currentsum=0;
currentsum = cumulativesum[j] - cumulativesum[i-1];
if ( currentsum == ksum)
count++;
}
}
cout<<"Total no. of subarray sum equals "<<ksum<<" is ";
cout<<count;
return 0;
}
About this post:
Siddharth Jha writes this post. In this post, we print the total number of subarrays having a sum equal to k using three nested. In another program, we used the concept of cumulative sum and showed the number of subarray sums equal to k using two nested loops.
title must be Subarray Sum Equals K leetcode solution 🙂
Great post
Great post