So, What if the numbers can also be negative?
We can't use sliding window algorithm then. First of all we will compute prefix sum and then sort it with their respective index (sort them as {prefixL[i],i}).Then we will apply binary search on it for every index i to look for element whose index j is greater than index i and whose value is equal to prefixL[i] + K. This will take \(\cal{O}(n \cdot \log(n))\) time.
Problem
Given a list of integers L = [A1, A2, A3, …, AN]. Where Ai ∈ I , 0 ≤ i ≤ N. You have to find shortest contiguous segment in the list which adds up to a given integer K. If there are more than one such segments, print one of them.
For example,
If L = [2, 1, 10, 1, 3, -4, -2, 20, 5, 5, 5, 1, 1] and K = 17 , The answer would be {4, 7}.
Code
Let's make problem even more intresting.
Problem
Given a list of integers L = [A1, A2, A3, …, AN]. Where Ai ≥ 0 , 0 ≤ i ≤ N. You have to find pair of shortest disjoint contiguous segment in the list each adding up to a given integer K and sum of size of segment is minimum. If there are more than one such pair of segments, print one of such pair.
For example,
If L = [2, 1, 3, 1, 4, 4, 1, 8, 1, 7] and K = 9 , The answer would be {{3, 5}, {6, 7}}.
Solution
Note that pairs of segments have to be disjoint. So, we can't simply say that the segments with least size will be the answer. Even in the given example {6, 7} and {7, 8} are two least size segments, but they have a common index which doesn't follow the condtition of being disjoint. Then, what should we do?
Let us take an index i, for each i we will find the least size segment in range [0, i] and (i, N). Doing this will ensure that the segments are disjoint. As far as searching segment in the ranges are concerned, we can find them by applying sliding window algorithm from both the sides.