CODEWITHSUNDEEP
calgorithm
prateek
prateek

Reputation: 1

Reducing Complexity finding the subarrays with a given sum

I am trying to code a problem where I have to find contiguous sub-arrays of a given array with a given sum. What I am trying to do is use a loop i from 0 to n and another from i to n and compute all sub-array sums using this. But I think that time complexity of the solution can be reduced further. I just can't figure out how. Is the problem convertible to DP? I need to find the total number of sub-arrays.

Upvotes: 0

Views: 383

Answers (1)

dejavu
dejavu

Reputation: 3254

For positive numbers only

Initialize a variable curr_sum as first element. curr_sum indicates the sum of current subarray. Start from the second element and add all elements one by one to the curr_sum. If curr_sum becomes equal to sum, then print the solution. If curr_sum exceeds the sum, then remove trailing elements while curr_sum is greater than sum.

This algo will give the first correct answer. There might be more than one subarray present as answer. ``

Complexity : O(n)

Upvotes: 1

Related Questions