Given an array and a integer k. You have to find a minimum length sub array such that sum of this sub array is equal to k. If found return starting and ending index ( 0 starting based ).
Examples :
Input : arr = {2, 2, -4, 3, -2} and k = 1
Output : 3 4
Explanation :
We have 3 sub array whose sum is 1, i.e (0,4) , (1,3) , (3,4)
Out of these sub array (3,4) has minimum length 2.
Input : arr = {0 , 1 , -1} and k = 0
Output : 0 0
Explanation :
We have 3 sub array whose sum is 0, i.e (0,2) , (0,0) , (1,2)
Out of these sub array (0,0) has minimum length 1.
Naive Approach – Iterate with two nested loop and check sum of all possible sub array and find the minimum one. Time Complexity – O(N^2) Efficient Approach – Idea is to use prefix sum of this array. The sum of a sub array is equal to prefix sum till ending index – prefix sum till starting index-1 . Consider this example – arr = {2, 2, -4, 3, -2} and k = 1 . pref_sum = {2, 4, 0, 3, 1}. Let ending index = 3 and starting index be 2. Then sum of sub array between these two index is prefix_sum[3] – prefix_sum[2-1] = 3 – 4 = -1. From above we can conclude this sum of sub array is pref_sum[ending] – pref_sum[starting – 1] . Case if starting index is 0, so pref_sum[-1] = 0. Iterate with one single loop and let this index as ending index of sub array . For this ending index we have to find a starting index such that the sum of this sub array is equal to k. we know that prefix_sum[ending] – prefix_sum[starting-1] = k. We can say that we have to find a index whose prefix_sum is prefix_sum[ending] – k. This index will be starting index – 1.

Implementation :
// C++ program to find the
// minimum length sub array
// array with the sum = k.
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum
// length sub array in the array
// with sum = k.
void MinLenSubArr(int* a, int n, int k)
{
// Variable to store minimum length
// Declare with maximum value not possible
int min_len = n+1;
// Variable to store sub array index
pair<int,int> index;
// Variable to store prefix sum
int pref_sum = 0;
// map to store the prefix sum as key
// along with index as value
map<int,int> prefix_sum_index;
// Base Case
prefix_sum_index[0] = -1;
// Loop to iterate through the array
for (int i = 0; i < n; ++i) {
// Add current value to prefix sum.
pref_sum += a[i];
// Let this index to be end
// And we will try to find out
// Starting index for a sub array
// such that sum will be k
// Let this index be srt
// Thus prefix_sum[end] - prefix_sum[srt-1] = k
// prefix_sum[end] = pref_sum
// Thus we have to check whether there exist
// a sum (pref_sum - k) in a map or not.
if(prefix_sum_index.find(pref_sum - k) !=
prefix_sum_index.end())
{
// We find a index srt-1 such that
// prefix_sum[end] - prefix_sum[srt-1] = k
// Length of this sub array is equal to end - srt + 1
// i is end & srt is prefix_sum_index[pref_sum - k] + 1
int srt = prefix_sum_index[pref_sum - k] + 1;
int len = i - srt + 1;
if(len < min_len )
{
// Update minimum length and index
min_len = len;
index = {srt,i};
}
}
// Update map
prefix_sum_index[pref_sum] = i;
}
if(min_len == n+1)
// We don't find any sub array
// whose sum is k
cout<< "No sub array with sum k" <<endl;
else
cout<< index.first <<" "<< index.second <<endl;
}
// Driver code
int main()
{
int a[] = { 2, 2, -4 , 3 ,-2 };
int n = sizeof(a) / sizeof(a[0]);
int k = 1;
MinLenSubArr(a, n, k);
return 0;
}