209. 長度最小的子數組

從前綴和到滑動窗口

題目要求範圍內總和 $\geq{\text{target}}$ 的最短子數組，存放的數字都 $\geq0$ 。 如果用前綴和的方式枚舉，是 $O(n^2)$ 的複雜度，那麼優化的方向有哪些？ 因為前綴和數組本身是遞增的，所以能用二分搜尋的方式找到合適的終點， 複雜度降低到 $O(n\log{n})$ ，還能繼續優化。

假設固定結尾 $j$ ，假設對於它來說，滿足條件的開頭位置在 $i$ ，而 $i+1$ 是不滿足的。 那麼對於後續的 $j+1$ ，因為存放的數字 $\geq0$ ， $i$ 必定也會滿足條件。 也就是說，在知道上一次滿足條件的位置 $i$ 之後，移動結尾位置之後，它完全不需要考慮 $i$ 以及之前的任何開頭。 更直白的說，如果 $nums[i]+\dots+nums[j])$ $\geq target$ ，那麼 $nums[i]+\dots+nums[j+1]\geq target$ 。 只要試著將 $i$ 往右，考慮 $nums[i+1], nums[i+2]\dots$ 直到總和不滿足，再去移動 $j$ 就行。

程式碼

1. 前綴和

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        vector<long long> preSum(n + 1);
        for(int i = 0; i < nums.size(); i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        if(preSum.back() < target) return 0;
        int res = n;
        for(int i = 0, j = 0; j < n; j++) {
            while(i <= j && preSum[j + 1] - preSum[i] >= target) {
                res = min(res, j - i + 1); // 列入參考
                i++; // 移動左邊
            }
            // 此時 nums[i] ~ nums[j] 的總和 < target
        }
        return res;
    }
};

此時可以發現前綴和數組沒有存在的必要，只要在移動 $i,j$ 時更新區間總和就好，
能省去一半的計算時間。

2. 滑動窗口

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        if(reduce(nums.begin(), nums.end(), 0) < target) return 0;
        int left = 0, right = 0;
        int n = nums.size();
        int res = n, sum = 0;
        while(right < n) {
            sum += nums[right++]; // 移動結尾位置
            while(sum >= target) {
                sum -= nums[left++]; // 不需要考慮 left 以及之前的位置, 減去 left 對應的數值
                res = min(res, right - left + 1);
            }
        }
        return res;
    }
};

恭喜你，這就是滑動窗口的經典實現，

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)\to O(1)$