Блог пользователя shivam565

Автор shivam565, история, 4 года назад, По-английски

How to find total number of subarrays with sum atmost k?

Constrains :
-1e4 <= a[i] <= 1e4
1 <= n <= 1e5

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
4 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

We can use sliding window technique to solve the problem.
Here, i and j represent starting and ending points of the sliding window.
Initially i = j = 0.
Now, we will traverse the whole array and try to add elements.

  • If sum < k, j++. So, number of sub-arrays produced = j-i. Also add arr[j] to the sum.
  • If sum >= k, we will subtract arr[i] from sum so that again sum<k. So, i++.
CODE
»
4 года назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Convert the statement to it's equivalent in terms of prefix sums i.e $$$pre_r - pre_l \lt = k$$$.

Now iterating over $$$r$$$, we need to find number of $$$l$$$ such that $$$pre_l \gt = pre_r - k$$$, which can be computed using ordered set of all $$$pre_l$$$.