Find number of subarrays containing pairs with sum K

I need help with a problem that appeared in one of the coding tests for a company. The problem was something like this -

Given an unsorted array of integers and an integer k, find the number of subarrays where there exists a pair of integers ai and aj (i != j) in the subarray such that ai + aj = k

I was not able to find this problem online. Is this solvable using the sliding window technique? Can anyone help me with this?

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)

do you mean something like for each pair count how many subarrays that pair contributes ?

Nope ,it is quite the opposite.
For every subarray i…j , check if it contains a pair s.t. sum is k.