209. Minimum Size Subarray Sum

題目網址：https://leetcode.cn/problems/minimum-size-subarray-sum/

題意：給一正整數 array nums 和一正整數 target, 返回滿足元素和 ≥ target 的長度最小的連續 subarray, 如果不存在這樣的 subarray 則返回 0。

進階：設計 $O(n \cdot log(n))$ time 和 $O(n)$ time 的演算法

Solution：

想法：利用 Sliding Window

• 先擴大窗口, 直到窗口裡的元素總和 sum ≥ target
• 此時, 開始縮小窗口, 並同時更新 res, 直到 sum < target
• 重複上述步驟, 直到 right 到 nums 的結尾

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0;
        const int n = nums.size();
        int res = n + 1, sum = 0;

        while (right < n) {
            sum += nums[right];
            ++right;

            while (sum >= target) {
                res = min(res, right - left); // 此時, sum 是符合要求的, 故在此更新 res
                sum -= nums[left];
                ++left;
            }
        }
        return (res == n + 1) ? 0 : res;
    }
};

• time：$O(n)$ ➔ nums 中的元素每個最多被遍歷 2 次(left, right)
• space：$O(1)$ ➔ 只需常數空間