力扣題目鏈接

1. 暴力解法

這道題的暴力解法是兩層嵌套for循環，第一層循環從 i = 0 開始遍歷至數組末尾，第二層循環從 j = i 開始遍歷至找到總和大于等于 target 的連續子數組，并將該連續子數組的長度與之前找到的子數組長度相比較，若這個子數組長度更短，則更新結果。并將初始長度設置為 INT32_MAX 或 nums.size() + 1，用于判斷是否不存在符合條件的子數組，通過判斷結果是否被賦值，若未被賦值就返回0，說明沒有符合條件的子序列。

//時間復雜度：O(n^2)
//空間復雜度：O(1)
class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int result = INT32_MAX; // 最終的結果int sum = 0; // 子序列的數值之和int subLength = 0; // 子序列的長度for (int i = 0; i < nums.size(); i++) { // 設置子序列起點為isum = 0;for (int j = i; j < nums.size(); j++) { // 設置子序列終止位置為jsum += nums[j];if (sum >= s) { // 一旦發現子序列和超過了s，更新resultsubLength = j - i + 1; // 取子序列的長度result = result < subLength ? result : subLength;break; // 因為我們是找符合條件最短的子序列，所以一旦符合條件就break}}}// 如果result沒有被賦值的話，就返回0，說明沒有符合條件的子序列return result == INT32_MAX ? 0 : result;}
};

2. 滑動窗口

上述暴力解法提交會超時。
所謂滑動窗口，就是不斷的調節子序列的起始位置和終止位置，從而得出我們要想的結果。
在暴力解法中，是一個for循環滑動窗口的起始位置，一個for循環為滑動窗口的終止位置，用兩個for循環 完成了一個不斷搜索區間的過程。滑動窗口只用一個for循環來完成這個操作。

而這個循環的索引，一定是表示 滑動窗口的終止位置。

下面是代碼隨想錄中給出的運用滑動窗口解決問題的過程，非常的簡潔明了：

• 窗口的結束位置 j 就是遍歷數組的指針，也就是for循環里的索引。i 則代表窗口的起始位置。

1. 窗口的結束位置 j 首先不斷右移并執行 sum +=nums[j] 計算當前從指針 i 到 j 的子數組之和。
2. 當sum >= target時，此時得到一個總和大于等于 target 的連續子數組，其長度為count = j - i + 1，此時需判斷該長度是否比已記錄的最短長度要小，若小于則更新最短長度。
3. 隨后，窗口的起始指針 i 開始左移，縮小窗口長度，注意可能存在左移后其子數組總和仍大于等于 target 的情況，所以此處判斷應該是 while 而不是 for，還需要將 i 原來指向的數值在 sum 中減掉。
4. 窗口的起始指針 i 左移至窗口中的子數組不滿足條件時，此時需要結束指針 j 開始右移，直至窗口中的子數組再次滿足條件，即跳轉至第1步，當 j == nums.size() 時，表示數組內全部可能的子數組遍歷完成，返回結果。
5. 最后同樣通過將初始長度設置為 INT32_MAX 或 nums.size() + 1，判斷是否不存在符合條件的子數組，通過判斷結果是否被賦值，若未被賦值就返回0，說明沒有符合條件的子序列。

//時間復雜度：O(n)
//空間復雜度：O(1)
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ans = nums.size() + 1;int sum = 0;for(int i = 0, j = 0; j < nums.size(); j++){sum +=nums[j];//注意這里使用while，每次更新 i（起始位置），并不斷比較子序列是否符合條件while(sum >= target){int count = j - i + 1; //取子序列的長度if(count < ans){ans = count;}//ans = ans < count ? ans : count;//這里體現出滑動窗口的精髓之處，不斷變更i（子序列的起始位置）sum -= nums[i];i++;}}//如果ans沒有被賦值的話，就返回0，說明沒有符合條件的子序列if(ans == nums.size() + 1) return 0;else return ans;//return ans == (nums.size() + 1) ? 0 : ans;}
};

關于時間復雜度，不要以為for里放一個while就以為是O(n^2)， 主要是看每一個元素被操作的次數，每個元素在滑動窗后進來操作一次，出去操作一次，每個元素都是被操作兩次，所以時間復雜度是 2 × n 也就是O(n)。