Subarray with given sum

Given an unsorted array A of size N that contains only non-negative integers, find a continuous sub-array which adds to a given number S.

 

Example 1:

Input:
N = 5, S = 12
A[] = {1,2,3,7,5}
Output: 2 4
Explanation: The sum of elements 
from 2nd position to 4th position 
is 12.

 

Example 2:

Input:
N = 10, S = 15
A[] = {1,2,3,4,5,6,7,8,9,10}
Output: 1 5
Explanation: The sum of elements 
from 1st position to 5th position
is 15.

 

method: sliding window

• Maintain start and last index to store and print these values 
• Iterate the complete array.
• Add array elements to current sum
• If current sum becomes greater than S, then remove elements starting from start index, till it become less than or equal to S, and increment start.
• if current sum becomes equals to S, then return the starting and last index.
• if the current sum never matches to S, then return -1.

c++ implementation:

    vector<int> subarraySum(int a[], int n, int s)
    {
        vector<int>v;
        int l=0;int r=0;int c=0;
        while(r<=n)
        {
            if(c==s)
           {
               v.push_back(l+1);
               v.push_back(r);
               return v;
           }
            else if(c>s)
            {
                c=c-a[l];
                l++;
            }
            else
            {
                c=c+a[r];
                r++;
            }
        }
         v.push_back(-1);
        return v;
    }

Time Complexity: O(N)
Space Complexity: O(1)