LeetCode 209 Minimum Size Subarray Sum

LeetCode

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:

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<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)).

算法思路：

N/A

注意事项：

1. 求最小值，所以min_len初始化最大值
2. 长度为i - j + 1写例子来计算

Python代码：

def 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)