Let us start with a problem
Problem
Given a list of integers L = [A1, A2, A3, …, AN]. Where Ai ≥ 0, 0 ≤ i ≤ N. You have to find the 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, 3, 1, 4, 4, 1, 8, 1, 7] and K = 9, The answer would be {6, 7}.
By Naive Approach
Find every possible segments and sum up elements present in it. This will have \(\cal{O}(n^2)\) time complexity.
Can we do better ?
By Prefix Sum
Compute the prefix sum of array L into another array prefixL (make sure to add an extra element "0" before the list) , for every index i in prefixL, search if an element exist with value prefixL[i] + K and return the indices of the segment with minimum length. We can search for element with help of Binary Search, which will take \(\cal{O}(\log(n))\) time. So, overall it will have \(\cal{O}(n \cdot \log(n))\) time complexity.
Can we still do better ?
By Sliding Window Algorithm
As the name suggest, we will use two vectors i and j to point at starting and ending element of the segment respectively. If the current sum of the segment is less than K then increase the index j and include the element in the sum. If the current sum of the segment is greater than K then increase the index i and exclude the from the sum. When the current segment sum is equal to K, store the indices if the segment length is less than the previous one. As the array is iterated once, So, time complexity will be \(\cal{O}(n)\).
Note: Some conditions have been added to ensure that i ≤ j and j < n.
What if the numbers can also be negative?