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:

Post a Comment