Wednesday, May 8, 2013

Continuous sub array adding to a number

Given an array having positive integers, find a continuous sub array which adds to a given number.?

Complexity:

Despite having two nested loops, this code runs in linear time because i and j never decrease, and can only be incremented O(N) times.

public class ContinousSum {

public static void findContinousArray(int A[], int target) {
for (int i = 0, j = 0, sum = 0; i < A.length; i++) {
while(j < A.length && sum < target) {
sum += A[j];
if(sum >= target)break;
j++;
}
if (sum == target) {
System.out.println("sub array indices" + i + "," + j);
return;
}
sum -= A[i];

}

}

public static void main(String[] args) {
int a[] = { 1, 2, 3, 4 };
findContinousArray(a, 5);

}
}

No comments: