# [leetcode] 209. Minimum Size Subarray Sum _ Algorithm Problem Solve for python

## 1. Problem

209. Minimum Size Subarray Sum

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 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.


Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1


Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0


Constraints:

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4

## 2. Solution

I solved this problem like this.

### 2.1. Time over solution

• I first solved this problem like this.
• I check all length of sum and this time complexity is O(n^2).
• n’s max value is 10^5, so this makes problem.
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
for l in range(1, len(nums)+1):
value = sum(nums[:l])
# check value
if value >= target:
return l

for i in range(0, len(nums)-l):
# value change
value = value - nums[i] + nums[i+l]

# check value
if value >= target:
return l

return 0


### 2.2. Good solution

• This solution used ‘Sliding window’. I I was greatly helped by AnthonyChao’s solution. Thank you so much!
• This solution works like this. The time complexity is just O(n).
• If sum between right and left >= target, move left cursor
• Else, move right cursor.
[2,3,1,2,4,3] total = 2,  left = 0, right = 0, ans = 987654321
^
[2,3,1,2,4,3] total = 5,  left = 0, right = 1, ans = 987654321
^ ^
[2,3,1,2,4,3] total = 6,  left = 0, right = 2, ans = 987654321
^   ^
[2,3,1,2,4,3] total = 8,  left = 0, right = 3, ans = 4
^     ^
[2,3,1,2,4,3] total = 6,  left = 1, right = 3, ans = 4
^   ^
[2,3,1,2,4,3] total = 10, left = 1, right = 4, ans = 4
^     ^
[2,3,1,2,4,3] total = 7,  left = 2, right = 4, ans = 4
^   ^
[2,3,1,2,4,3] total = 6,  left = 3, right = 4, ans = 4
^ ^
[2,3,1,2,4,3] total = 9,  left = 3, right = 5, ans = 4
^   ^
[2,3,1,2,4,3] total = 7,  left = 4, right = 5, ans = 2
^ ^

class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
ans = 987654321
left, total = 0, 0

for right in range(len(nums)):
total += nums[right]
while total >= target:
ans = min(ans, right - left + 1)
total -= nums[left]
left += 1

return ans if ans != 987654321 else 0