Help in Subarray with given Sum

general
, , ,
1

Ques link :
https://practice.geeksforgeeks.org/problems/subarray-with-given-sum/0

I want to solve this question by STL only and mainly by unordered_map.
According to me solution is in O(N) only.
But I am getting TLE. I think find() function’s time complexity going from O(1) to worst case!!?

Here is my attempt:
https://ide.geeksforgeeks.org/m1QLsFBjnd

So how to solve this question efficiently w/o Sliding Window technique?

2

unordered_map::find is O(N) in the worst case:

and some challenge authors will exploit this.

1 Like
3

@ssjgz so there is no way to easily do this with unordered_map! we need to switch over to sliding window?? or there is any other easy method?

4

Dunno :slight_smile: Why not just try a std::map?

1 Like
5

@ssjgz bro map also giving tle!! i am so confused now!!

6

10^7 is way too much for a map.
Hint : All elements are positive.

1 Like
7

actually i am a new to cp… so don’t know many of the cool algos so can you pls guide me? @everule1