# 209 - Minimum Size Subarray Sum

解法一 - Sliding Window

做法滿直覺的，就是一直擴張 windowEnd，如果發現 windowSum 已經比 s 大，那就開始縮減 window，直到走到 nums 的尾巴。

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int windowSum = 0, windowStart = 0;
        int minWindowSize = numeric_limits<int>::max();

        for(int windowEnd=0; windowEnd<nums.size(); windowEnd++) {
            windowSum += nums[windowEnd];

            while(windowSum >= s) {
                minWindowSize = min(minWindowSize, windowEnd-windowStart+1);
                windowSum -= nums[windowStart];
                windowStart++;
            }
        }

        return minWindowSize == numeric_limits<int>::max() ? 0 : minWindowSize;
    }
};

時間複雜度是 O(n)，跑起來的效率如下：

Runtime: 12 ms, faster than 66.67% of C++ online submissions for Minimum Size Subarray Sum. Memory Usage: 9.9 MB, less than 82.35% of C++ online submissions for Minimum Size Subarray Sum.

解法二 - Binary Search

滿酷的，沒想到還可以用 binary search，先記一下。