# TLE in Hashing O(N)

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 my attempt:

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

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

O(n). updated So how to solve this by STL? @aditya_akash

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