Sub array with a given sum

105 Views Asked by At

(The given problem is referred from : https://practice.geeksforgeeks.org/problems/subarray-with-given-sum-1587115621/1?page=1&difficulty[]=0&curated[]=1&sortBy=submissions )

I tried a solution to the above problem but it failed for large values for N and S.

I attempted the following solution to the above problem:

class Solution
{
    public:
    //Function to find a continuous sub-array which adds up to a given number.
    vector<int> subarraySum(int arr[], int n, long long s)
    {
        // Your code here
        long long sum=arr[0];
        int first=0,last=0;
        vector<int> v{-1,-1};
        vector<int> a{-1};
        if(arr[0]==s)
        {
            v[0]=1;
            v[1]=1;
            return v;
        }
        for(int i=0;first<n && last<n;i++){
            if(sum>s){
                if(first==last && (last+1<n)){
                    sum=sum-arr[first]+arr[first+1];                    
                    first++;
                    last++;
                }
                else{
                    if(first==last && last==n-1){
                        break;
                    }
                    if(first<last)    
                    {   sum=sum-arr[first];
                        first++;
                    }
                }            else if(sum<s){
                last++;
                sum+=arr[last];
            }
            else if(sum==s){
                v[0]=first+1;
                v[1]=last+1;
                return v;
            }
        }
        return a;
    }
};

In the code, 'first' and 'last' are the indexed of the first and the last element of the sub-array. (Edit: The edited code works!, thanks for all the help!)

0

There are 0 best solutions below