題目

給定一個含有 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