题目:
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 <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104
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)).
题目解析:
这里我们可以使用 sliding window 的技巧。
我们可以使用两个 pointers,一个是 start 一个是 end,两个指针都从array的开头开始。
向右移动 end 指针来提高 window 的大小,每一次移动指针都把 nums[end] 添加到现在的和。
当这个和大于或等于 target 时,我们要开始缩短 subarray 的长度。于是我们开始移动 start 这个指针来缩小 window 的大小。通过不停的向右移动 start 指针,直到找到最短的 subarray 的长度。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
start = 0
curr_sum = 0
min_len = float('inf')
for end in range(len(nums)):
curr_sum += nums[end]
while curr_sum >= target:
min_len = min(min_len, end - start + 1)
curr_sum -= nums[start]
start += 1
return min_len if min_len != float('inf') else 0
Time complexity 是 O(n)。
Space complexity 是 O(1)。