Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.
Input: s = 7, nums = [2,3,1,2,4,3]
Explanation: the subarray [4,3] has a minimal length under the problem constraint.
In order to come up with the strategy behind this solution, you must first understand that you will need to use the Sliding Window Algorithm. If you are not completely confident with what that algorithm is, and how to identify when a problem will require the sliding window — please read this article first.
Here’s the code for Leetcode 209:
The strategy is as follows:
- Maintain pointers for the beginning and end of your window
- Maintain a value which represent the minimum size of your window so far
- Handle edge cases
- Loop through the array, building a sum from each element
- When your sum reaches the target value,
s, then you should stop moving the window end index and start moving the window start index. Before you move the window start index, you should store what the current size of the window is in your minWindowSize
- Once we have found our first window, we should move the windowStart so that we can try to find another window in the array which contains our sum (a potentially smaller window!)
- If we reach the end of our array, and have not found any window which satisfies our sum, then our minWindowSize will be unchanged, and still equal to Integer.MAX_VALUE, so we know that we should just return 0 to represent “not found”.
Thanks for the claps, feel free to leave a comment if you want more insight.