題目

209. Minimum Size Subarray Sum 這題給定一個正整數陣列，以及一個正整數target，要求陣列中最短的子陣列和大於或等於target。

解題思路

首先，我們可以先想到使用暴力法來解決，假設一個陣列長度為n，所有自陣列的組合從1到n，只要窮舉出來並且求和去判斷即可。

for i in range(len(nums)):
    for j in range(i, len(nums)):
        val = sum(nums[i:j+1])

此外，求和的部分，我們可以透過presum的技巧來優化，將複雜度壓到O(1)

實作

presum = [0]
total = 0
for num in range(nums):
    total += num
    presum.append(total)

for i in range(len(nums)):
    for j in range(i, len(nums)):
        val = presum[j+1] - presum[i]

這樣一來時間複雜度是$O(n^2)$，我們會發現其實當中有一些不必要的計算，舉例來說，如果有一個子矩陣nums[i:j]和已經大於等於target，那麼我們其實就沒有必要繼續看nums[i:j+1]和nums[i-1:j]了，跟著這個思路，我們其實可以透過前後指針來解。

當我們目前的和小於目標時，後指針就往後一步(加大矩陣)，當目前的和大於或等於目標的時候就將前指針往後一步(縮小矩陣)，並且紀錄目前的長度，這個過程中，我們會計算到所有符合的子矩陣。

實作

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        presum = [0]
        val = 0
        for num in nums:
            val += num
            presum.append(val)
        
        minlen = len(nums)+1
        head = 0
        tail = 1
        while head < tail and tail < len(nums)+1:
            x = presum[tail] - presum[head]
            if x < target:
                tail += 1
            else:
                length = tail - head
                if length < minlen:
                    minlen = length
                head += 1
        if minlen == len(nums)+1:
            return 0
        return minlen