在這個系列的部落格中，我們根據LeetCode官方給出的每個題目的出現頻率，整理并收錄了每個類别裡高頻出現的題目，從簡單到中等再到困難，為你提供解題技巧和最佳實踐。我們将介紹常見的算法思想，如貪心算法、動态規劃、回溯算法等，希望能幫助你提高算法水準，成為你進入人工智能行業敲門磚。
209. 長度最小的子數組（難度3/頻率4）
給定一個含有 n 個正整數的數組和一個正整數 s ，找出該數組中滿足其和 ≥ s 的長度最小的 連續子數組，并傳回其長度。如果不存在符合條件的子數組，傳回 0。
示例 1:
輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2解釋：子數組 [4,3] 是該條件下的長度最小的子數組。
示例 2:
輸入：target = 4, nums = [1,4,4] 輸出：1
解題思路
做深度學習視覺的同學應該對操作數組很熟悉，數組操作中一個重要的方法：滑動視窗。
所謂滑動視窗，就是不斷的調節子序列的起始位置和終止位置，進而得出我們要想的結果。
在暴力解法中，都是每次确定子數組的開始下标，然後通過兩個for循環得到長度最小的子數組，是以時間複雜度較高。
那麼滑動視窗如何用一個for循環來完成這個操作呢。首先要思考如果用一個for循環，那麼應該表示滑動視窗的起始位置，還是終止位置。如果隻用一個for循環來表示滑動視窗的起始位置，那麼如何周遊剩下的終止位置？此時難免再次陷入暴力解法的怪圈。
是以隻用一個for循環，那麼這個循環的索引，一定是表示滑動視窗的終止位置（想到這點非常重要）。
那麼問題來了， 滑動視窗的起始位置如何移動呢？以題目中的示例來舉例，s=7
在本題中實作滑動視窗，主要确定如下三點：
- 視窗内是什麼？
- 如何移動視窗的起始位置？
- 如何移動視窗的結束位置？
視窗就是 滿足其和 ≥ s 的長度最小的 連續 子數組。
視窗的起始位置如何移動：如果目前視窗的值大于s了，視窗就要向前移動了（也就是該縮小了）。
視窗的結束位置如何移動：視窗的結束位置就是周遊數組的指針，也就是for循環裡的索引。
解題的關鍵在于視窗的起始位置如何移動，如圖所示：
可以發現滑動視窗的精妙之處在于根據目前子序列和大小的情況，不斷調節子序列的起始位置。進而将O(n^2)暴力解法降為O(n)。
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
res = float("inf") # 定義一個無限大的數
sum, index = 0, 0
for i in range(len(nums)):
sum += nums[i]
while sum >= s:
res = min(res, i-index+1) # 最小的索引
sum -= nums[index] # 移動起始位置
index += 1
return 0 if res==float("inf") else res 題目總結
本題其實有一個重點，就是真正了解滑動視窗，怎麼定義滑動視窗兩個指針的移動，這道題可以給數組操作帶來進一步的了解。