<div>
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [nums<sub>l</sub>, nums<sub>l+1</sub>, ..., nums<sub>r-1</sub>, nums<sub>r</sub>] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Example 1:
<pre>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. </pre>
Example 2:
<pre>Input: target = 4, nums = [1,4,4] Output: 1 </pre>
Example 3:
<pre>Input: target = 11, nums = [1,1,1,1,1,1,1,1] Output: 0 </pre>
Constraints:
1 <= target <= 10<sup>9</sup>1 <= nums.length <= 10<sup>5</sup>1 <= nums[i] <= 10<sup>5</sup>
Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).</div>
算法思路：
N/A
注意事项：
- 求最小值，所以min_len初始化最大值
- 长度为i - j + 1写例子来计算
Python代码：
1
2
3
4
5
6
7
8
9def minSubArrayLen(self, target: int, nums: List[int]) -> int:
min_len, num_sum, left = float('inf'), 0, 0
for i in range(len(nums)):
num_sum += nums[i]
while num_sum >= target:
min_len = min(min_len, i - left + 1)
num_sum -= nums[left]
left += 1
return 0 if min_len == float('inf') else min_len
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
