209-minimum-size-subarray-sum.md

209. Minimum Size Subarray Sum - 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

示例: 

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

---

题目标签：Array / Two Pointers / Binary Search

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
cpp	4 ms	2.5 MB

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        if (s > accumulate(nums.begin(), nums.end(), 0)) return 0;
        if (s == 0) return 0;
        vector<int> acc;
        acc.push_back(0);
        for (int n : nums) {
            acc.push_back(n + acc.back());
        }
        int p = 0, q = acc.size() - 1;
        int res = nums.size();
        while (acc[q] - acc[p] >= s && q > p) {
            while (acc[q] - acc[p] >= s) {
                p++;
            }
            p--;
            while (acc[q] - acc[p] >= s) {
                q--;
            }
            q++;
            res = min(res, q - p);
            while (p >=0 && q < acc.size()) {
                p--;
                q--;
                if (acc[q] - acc[p] >= s) {
                    break;
                }
            }
        }
        return res;
    }
};
static auto _ = [](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();