Be the first user to complete this post
|
Add to List |
Find the subarray with sum to a Given Value.
Objective: Given an array (non-negative) and an integer, Find the Subarray whose sum is equal to the given integer.
Examples:
int[] arrA = { 25, 12, 14, 22, 19, 15, 10, 23 }; Integer = 55
Output
: 55 is found between indexes 2 and 4 And Elements are : 14 22 19
Approach :
Naive Approach: Use 2 loops . Time Complexity - O(n2).
Better Approach: Time Complexity - O(n)
- Idea is to keep adding all the elements to the currSum
- Keep checking if the currSum<Sum
- If currSum gets greater than the Sum then start reducing the currSum from the beginning of the array using "start"if any time currSum=Sum, Stop and return
Code:
Output:
55 is found between indexes 2 and 4 And Elements are : 14 22 19
Also Read: