題目
給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) target。
找出該數(shù)組中滿足其和 ≥ target 的長度最小的連續(xù)子數(shù)組 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其長度婚夫。如果不存在符合條件的子數(shù)組，返回 0寥闪。
方法一
分別計算每一種方式的子數(shù)組長度仁连，最終將最小的輸出。
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 來存放最小子數(shù)組的長度嘀韧。
- 首先篇亭，end 不斷增加直至 total >= target，記錄 ans锄贷。
- 之后译蒂，start 右移曼月，使得 total < target，end右移直至 total >= target柔昼，判斷此次子數(shù)組的長度與之前子數(shù)組長度的大小哑芹，存儲小的那個。
- 不斷循環(huán)捕透，直至最末端聪姿。
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
