209. Minimum Size Subarray Sum

sliding window O(n) 另外有个O(nlogn)的维护presum和map

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        int res = INT_MAX;
        for (int r = 0, l = r; r < n; ++r) {
            sum += nums[r];
            while (sum >= s && l <= r) { // 这里必须是<=因为单个数就有可能大于s
                res = min(res, r + 1 - l); // 因为是求最短所以可以实时更新res
                sum -= nums[l++];
            }
        }
        return (res == INT_MAX ? 0 : res);
    }
};

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        int res = INT_MAX;
        for (int l = 0, r = l; l < n; ++l) {
            while (r < n && sum < s) {
                sum += nums[r++];
            }
            if (sum >= s) {
                res = min(res, r - l);
            }
            sum -= nums[l];
        }
        return (res == INT_MAX ? 0 : res);
    }
};