题目
给定一个含有 n 个正整数的数组和一个正整数 target。
找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0。
方法一
分别计算每一种方式的子数组长度,最终将最小的输出。
class Solution(object):
def minSubArrayLen(self, target, nums):
old = 0
for j in range(len(nums)):
i = j
result = 0
new = 0
while result < target and i < len(nums):
result = result + nums[i]
if result < target:
i = i + 1
else:
new = i - j + 1
if old == 0 or old > new and new != 0:
old = new
return old
※ 会显示超出时间限制
方法二:滑动窗口
- 设置 start 和 end 来存放起始位置和终止位置的下标,total 来存放起始位置到终止位置的元素和,ans 来存放最小子数组的长度。
- 首先,end 不断增加直至 total >= target,记录 ans。
- 之后,start 右移,使得 total < target,end右移直至 total >= target,判断此次子数组的长度与之前子数组长度的大小,存储小的那个。
- 不断循环,直至最末端。
class Solution(object):
def minSubArrayLen(self, target, nums):
start = end = 0
total = 0
ans = len(nums) + 1
while end < len(nums):
total = total + nums[end]
while total >= target:
ans = min(ans, end - start + 1)
total = total - nums[start]
start = start + 1
end = end + 1
if ans == len(nums) + 1:
return 0
else:
return ans
网友评论