There is obviously a naive brute force in O(n^3). For every subarray, check if it is `valid`

or not ?

We can speed it up to O(n^2) by counting in clever way.

Both technique uses an O(n) space for HashSet/unorderd_map.

We can further optimise it to O(nlogn) time.

Imagine a pair satisfying the condition at i, j. This allows you to take i*(n-j + 1) subarrays.

We can use this observation.

Let’s iterate `i`

from `1..n`

for `i`

, we want to find closes `j`

s.t. `j>i`

and `a[i] + a[j] =k`

. (Easily doable in logn time ).

For this pair, let’s add `i*(n-j+1)`

to our answer.

~~To avoid overcounting subarrays, we should keep track of previous ~~`i`

and previous `j`

##
How to avoid overcounting?

Lets start with an observation consider two pairs `{i1,j1}`

and `{i2,j2}`

If `{i2,j2}`

is completely inside `{i1,j1}`

then we can get rid of `i1,j1`

as `i2,j2`

will count every subarray.

Let’s maintain a stack to achieve this.

(we will push the pair `{i,j}`

in stack)

In the loop for `i = 1..n`

Let’s find closest `j`

as described above.

Pop all the elements from stack which are `completely larger than curr pair`

. Since i is always increasing, we can only check for j’s .

This will also maintain out stack in `increasing j`

.

After that we need to count subarray from every element in stack.

int pi = 0;

For (i,j) in stack(bottom of stack to top):

ans+=(i-pi)*(n-j+1);

pi = i;

This should avoid overcounting.

Since, every element is popped and pushed atmost once . Time is O(n)