# Find subarrays with a given sum in an array

Posted in  Last updated on November 30, 2023

## Problem

Given an unsorted array of nonnegative integers, find a continuous subarray which adds to a given number. Print the starting and ending indices of the subarray.

#### Sample Input

`[1, 4, 20, 3, 10, 5] k = 33`

#### Sample Output

`2 4`

### Approach

We can initialize two pointers as ``` left ``` and ``` right ``` both to index 0 and a variable ``` sum=0 ``` to track sum of subarrays. When we see that the ``` sum ``` is greater than ``` k ``` , we decrement the sum by the element at ``` left ``` index and increment ``` left ``` . When the sum of the subarray is smaller than ``` k ``` , we add an element at ``` right ``` index to ``` sum ``` and increment ``` right ``` . The time complexity of this approach is O(N).

#### C++

```#include<bits/stdc++.h>
using namespace std;
int main(){
int a={10, 4, 22, 4}, k = 22;
int n = sizeof(a)/sizeof(a);
int l=0, r=0;
int sum = 0;
while(r<n)
{
if(sum==k) break;
//we found the subarray
if(sum>k) sum-=a[l++]; //decrement from left
if(sum<k) sum+=a[r++]; //increment from right
}
cout<<l<<" "<<r-1;
}
```

#### Output

`2 2`

#### C

```#include<stdio.h>
void main(){
int a={10, 4, 22, 4}, k = 22;
int n = sizeof(a)/sizeof(a);
int l=0, r=0;
int sum = 0;
while(r<n)
{
if(sum==k) break; //we found the subarray
if(sum>k) sum-=a[l++]; //decrement from left
if(sum<k) sum+=a[r++]; //increment from right
}
printf("%d %d",l,r-1);
}
```

#### Output

`2 2`

#### Python

```a=[10, 4, 22, 4]
k = 22
n = 4
l = 0
r = 0
sum = 0
while r<n:
if(sum==k):
break #we found the subarray
if(sum>k):
sum-=a[l] #decrement from left
l+=1
if(sum<k):
sum += a[r] #increment from right
r+=1
print(l,r-1)```

#### Output

`2 2`