TLE in Hashing O(N)

general
, , ,
1

Ques- Here I need to find the sub-array with given sum but I am constantly getting TLE. According to me my solution is in O(n).
Here is the question link

Here is my attempt:

Afaik Unordered map find() also works in O(1). So what’s causing TLE error?
Thanks in advance!

2

One reason of TLE might be that the worst case complexity of unordered map is O(n). :slight_smile:

1 Like
3

@aditya_akash o(n) or o(n^2)??

4

O(n). updated :slight_smile:

5

So how to solve this by STL? @aditya_akash

6

I don’t think any STL is required to solve this question. You can use the concept of two pointers to calculate the sum of possible sub arrays.

You may refer this code. 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define M 1000000007
#define inf 1e18
#define all(a) (a).begin(),(a).end()

int main()
{

    //boost
    //double const pi = 3.14159265358979;
    int t,k,i,j;
    //ll M =1000000007;
    int n;
    cin>>t;
    while(t--)
    {
        int sum;
        cin>>n>>sum;
        int a[n];
        for(i=0;i<n;i++)cin>>a[i];
        i=0;
        j=0;
        ll cur=0;
        pair<int,int> ans = {-1,-1};

        for(i=0;i<n;i++) {
            if(i>j){
                j=i;
                cur=0;
            }
            while(j<n && cur + a[j]<=sum) {
                cur += a[j];
                if(cur != sum)
                    j++;
                //cerr<<cur<<" "<<i<<" "<<j<<"\n";
            }
            if(cur == sum ){
                ans = {i,j};
                break;
            }
            cur -= a[i];
        }
        if(ans.fi==-1) cout<<"-1\n";
        else {
            cout<<ans.fi +1<<" "<<ans.se+1<<"\n";
        }
    }
	return 0;
}
1 Like