209. Minimum Size Subarray Sum
Array, Binary Search, Prefix Sum, Sliding Window, Review, AMateList ·Problem Statement
link: LeetCode.cn LeetCode
Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Example:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Input: target = 4, nums = [1,4,4]
Output: 1
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Solution Approach
The algorithm utilizes a sliding window approach to find the minimal length of a subarray with a sum greater than or equal to the target.
Algorithm
- The algorithm employs two pointers, ‘left’ and ‘right’, to define a sliding window over the array.
- It expands the window by moving the ‘right’ pointer while maintaining the sum of elements within the window.
- When the sum meets or exceeds the target, it updates the result with the minimum length of the subarray found so far and shrinks the window by moving the ‘left’ pointer, aiming to find the shortest subarray length.
Implement
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
res = float('inf')
left = 0
right = 0
pre_sum = 0
while right < n:
pre_sum += nums[right]
while pre_sum >= target:
res = min(res, right - left + 1)
pre_sum -= nums[left]
left += 1
right += 1
return res if res != float('inf') else 0