Find subarrays with a given sum in an array

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[4]={10, 4, 22, 4}, k = 22;
int n = sizeof(a)/sizeof(a[0]);
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[4]={10, 4, 22, 4}, k = 22;
int n = sizeof(a)/sizeof(a[0]);
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

People are also reading:

• Find Maximum Subarray Sum
• Maximum Sum Circular Subarray
• Find the maximum product of two integers in an array
• Sort binary array in linear time
• Merge Two Sorted Arrays in-place
• Print all subarrays with 0 sum
• Count Inversions
• Hybrid QuickSort Algorithm
• Quicksort using Dutch National Flag Algorithm
• In-place vs out-of-place algorithms