【題目鏈接】
209. 長度最小的子數組
【題目描述】
【題解】
方法一：滑動窗口
本題可以使用雙指針算法，定義兩個指針l和r分別表示子數組的開始位置和起始位置，sum數組存儲的從l到r區間內所有元素的和。初始狀態下，l和r都指向下標0，sum的值為0。
每一輪迭代，將nums[r]添加到sum中，如果sum≥target，則更新子數組的最小長度，此時的最小長度為r-l+1，然后將nums[l]從sum中減去并將l右移，直到sum＜target，在這個過程中同樣需要更新子數組的最小長度。
在每一輪迭代后，將r右移。
【AC代碼】
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int l = 0, r = 0, n = nums.size();int sum = 0, res = 1e9;while(r < n) {sum += nums[r];while(sum >= target) {res = min(res, r - l + 1);sum -= nums[l];l++;}r++;}if(res == 1e9)return 0;return res;}
};
方法二：前綴和+二分查找
閱讀題目可以發現，其中出現了子數組的和，而前綴和算法可以在常數時間內通過前綴和數組計算任意區間的和，避免重復計算，從而提高查詢效率。同時，這道題保證了數組中每個元素都為正，所以前綴和一定是遞增的，這一點保證了二分的正確性。如果題目沒有說明數組中每個元素都為正，這里就不能使用二分來查找這個位置了。
為了使用二分查找，需要額外創建一個數組sums用于存儲數組nums的前綴和，其中sums[i]表示從nums[0]到nums[i?1]的元素和。得到前綴和之后，對于每個開始下標i，可通過二分查找得到大于或等于i的最小下標left，使得sums[left]?sums[i?1]≥target，并更新子數組的最小長度（此時子數組的長度是left?(i?1)）。由于二分查找的終止條件是left==right，因此此處找到的最小下標為right或者left。
【AC代碼】
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();if (n == 0) return 0;int res = 1e9;vector<int> sums(n + 1, 0);for (int i = 1; i <= n; ++i) {sums[i] = sums[i - 1] + nums[i - 1];}// 提前判斷整個數組和是否小于target，直接返回0if (sums[n] < target)return 0;for (int i = 1; i <= n; i++) {int left = i, right = n;while (left < right) {int mid = left + right >> 1;if (sums[mid] - sums[i - 1] >= target) {right = mid;} else {left = mid + 1;}}// 檢查left是否有效，且對應的和滿足條件if (left <= n && sums[left] - sums[i - 1] >= target) {res = min(res, left - i + 1);}}return res == 1e9 ? 0 : res;}
};
【思考&收獲】
1.閱讀題目，題目要求的是大于等于target的數組，第一次讀題的時候看成了等于target，卡住了一段時間。
2.數組中每個元素都為正，則前綴和一定是遞增的，這一點保證了二分的正確性，可以考慮使用二分查找。
)
