题目链接
https://leetcode.com/problems/minimum-size-subarray-sum/
题目描述
给定一个正整数数组nums和正整数target,找出nums中元素和大于等于target的最短子串,如果没有符合条件的子串,则返回0。
示例
输入:target = 7,nums = [2,3,1,2,4,3]
输出:2
子串[4,3]是满足条件的最短子串。
解题思路
此题求最短子串,可以由滑动窗口算法来求解。如果窗口内元素和小于target,则子串扩张,直到窗口内元素和大于等于target,找到一个可行解。然后右指针不动,左指针右移,去优化这个可行解,试图找到长度更短的子串。
注意要在确保找到一个可行解后更新结果,因此更新子串长度应该放在内层循环的开始,因为这样设置更新时能够保证当前窗口内元素和大于等于target。
Python实现
注意需要在最后判断res有没有更新,如果res仍等于float('inf'),说明nums中没有满足条件的子串,此时应当返回0。(要重视此类细节,即对于找不到符合条件的结果时如何返回)
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left,right = 0,0
res = float('inf')
cur_sum = 0
while(right <len(nums)):
s = nums[right]
right += 1
cur_sum += s
while(cur_sum >= target):
res = min(res,right-left)
d = nums[left]
left += 1
cur_sum -= d
return 0 if res == float('inf') else res