algo-aha

全非负数意味着，preprod[]数组单调递增，可以用滑动窗口解法

全正数数组、乘积<K的子段数

• https://leetcode.com/problems/subarray-product-less-than-k/

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    // 因为 k<2^20, nums[i]<2^10，小于k的乘积prod*nums[i]<2^30不会溢出
    if (k <= 1) return 0;

    int prod = 1, ans = 0;
    for (int hi = 0, lo = 0; hi < nums.size(); hi++) {
        prod *= nums[hi];
        while (prod >= k) {
            prod /= nums[lo];
            lo++;
        }
        // 以hi结尾的子段积都满足：[lo..hi], [lo+1,hi], ..., [hi,hi]
        ans += hi - lo + 1;
    }
    return ans;
}

全正数数组、和>=K最短子段长

• https://leetcode.com/problems/minimum-size-subarray-sum/

int minSubArrayLen(int k, vector<int>& nums) {
    const int N = nums.size();        
    int sum = 0, ans = INT_MAX;
    for (int hi = 0, lo = 0; hi < N; hi++) {
        sum += nums[hi];
        while (sum >= k) { 
            ans = min(ans, hi - lo + 1);
            sum -= nums[lo];
            lo++;
        }
    }
    return ans != INT_MAX ? ans : 0;
}

扩展：有负数数组的子段和，可以用 子段和的presum解法