Given an array of numbers and a sum, how to check if there is any sub-array with the given sum.
For example consider an array A = [7, 2, 9, 1, 5], and the sum is 12, then we can find a sub-array [2, 9, 1] which sums up to 12. So the answer is Yes. If we want to check for sum 14, we can not find a sub-array with that sum.
A simple method is to check if a sum can be found for all possible sub-arrays. This solution takes O(n3) time.
A more efficient method is the sliding window method. We maintain two indices, one indicates the beginning of the window, and the other indicates the ending of the window.
While iterating through the elements, we increment the end-index as long as the current sum is less than or equal to the target. If we find the target sum, then we are done. If we exceed the target sum, we deduct the beginning elements from the current sum until it is less than or equal to target sum.
This approach takes O(n) time. Here is the C++ code.