題目描述

給定一個含有 n 個正整數的數組和一個正整數 target 。

找出該數組中滿足其總和大于等于 target 的長度最小的 子數組 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其長度。如果不存在符合條件的子數組，返回0。

示例 1：

輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數組 [4,3] 是該條件下的長度最小的子數組。

示例 2：

輸入：target = 4, nums = [1,4,4]
輸出：1

示例 3：

輸入：target = 11, nums = [1,1,1,1,1,1,1,1]
輸出：0

解題方法

在力扣中，暴力法已經超時，此處不說明暴力法，可參考代碼隨想錄網站說明

滑動窗口法

參考視頻代碼隨想錄

所謂滑動窗口，就是不斷的調節子序列的起始位置和終止位置，從而得出我們要想的結果。
滑動窗口用一個for循環來完成這個操作。
首先要思考 如果用一個for循環，那么應該表示 滑動窗口的起始位置，還是終止位置。
如果只用一個for循環來表示 滑動窗口的起始位置，那么如何遍歷剩下的終止位置？
此時難免再次陷入 暴力解法的怪圈。
所以 只用一個for循環，那么這個循環的索引，一定是表示 滑動窗口的終止位置。

可以發現滑動窗口的精妙之處在于根據當前子序列和大小的情況，不斷調節子序列的起始位置。從而將O(n^2)暴力解法降為O(n)。

代碼如下：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int result = INT32_MAX;int sum = 0;    //滑動窗口內的數字和int subL = 0;   //滑動窗口的長度int i = 0;  //起始位置for(int j = 0; j < nums.size(); j++){sum += nums[j];while(sum >= target){subL = j - i + 1;result = result < subL ? result : subL;sum -= nums[i++];}}return result == INT32_MAX ? 0 : result;}
};

時間復雜度：O(n)
空間復雜度：O(1)