题意

正值数组中,求最短的连续区间,使其区间上值的和大于等于给定值.

限制:

数组长度不大于$10^{5}10^5$

数组中值不大于$10^{4}10^4$

方法

二分法

首先,因为数组元素全为正,那么长度为i的所有区间的和的最大值,一定小于长度为i+1的区间和的最大值.

因此,随着区间长度上升,其区间和最大值单调递增

对于有单调性的,想到二分法

通过二分区间长度,检查最大值是否大于给定的target

以题目样例数据[1,2,4,4,1,1,1],9 为例,l,r,m均表示区间长度,其中m为l,r的平均数

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int minSubarray(vector<int>& nums, int target) {
        // write code here
        long long all = 0;
        for(int i = 0;i<nums.size();i++){
            if(nums[i] >= target)return 1; // 某个元素直接大于 target
            all += nums[i];
        }
        if(all < target){ // 全部的和都不满足
            return 0;
        }
        // 左不满足,右满足
        int l = 1;
        int r = nums.size();
        while(l+1<r){
            int m = (l+r)/2;
            bool ok = false;
            for(int i = 0;i <= nums.size() - m;i++){
                long long s = 0;
                for(int j = 0;j<m;j++){ // 计算 nums[i..i+m)的和
                    s+=nums[i+j];
                }
                if(s >= target){ // 枚举每个长度为m的和
                    ok = true;
                    break;
                }
            }
            if(ok){ // 方案可行
                r = m;
            }else{
                l = m;
            }
        }
        return r;
    }
};

复杂度分析

时间复杂度: 最坏情况,每个位置计算了当前长度的所有和,所以时间复杂度为$O(n^2\cdot log(n))O(n^2\; \backslash cdot\; log(n)\; )$

空间复杂度: 额外的空间是常数个变量,所以空间复杂度为$O(1)O(1)$

前缀和优化时间效率

注意到上面每次求和,都是$O(n)O(n)$,这样总的时间复杂度就很高,如果能加快求和的效率,能优化时间复杂度

考虑 $pre[i]pre[i]$储存了从开始到第i个值的和

那么如果要求 第i到第j个数的和,只需要计算$pre[j]-pre[i-1]pre[j]-pre[i-1]$即可

所以通过增加一个前缀和数组,把每次求和效率优化到$O(1)O(1)$

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int minSubarray(vector<int>& nums, int target) {
        // write code here
        vector<long long> pre(nums.size()+1,0); // 前缀和
        for(int i = 0;i<nums.size();i++){
            if(nums[i] >= target)return 1; // 某个元素直接大于 target
            pre[i+1]=pre[i] + nums[i];
        }
        if(pre[nums.size()] < target){ // 全部的和都不满足
            return 0;
        }
        // 左不满足,右满足
        int l = 1;
        int r = nums.size();
        while(l+1<r){
            int m = (l+r)/2;
            bool ok = false;
            for(int i = 0;i <= nums.size() - m;i++){ // 枚举每个长度为m的和
                if(pre[i+m] - pre[i] >= target){ // 利用前缀和计算
                    ok = true;
                    break;
                }
            }
            if(ok){ // m满足
                r = m;
            }else{
                l = m;
            }
        }
        return r;
    }
};

复杂度分析

时间复杂度: 通过前缀和数组的优化,虽然多了一次预处理初始化前缀和的时间,但总的处理时间变为了$O(n\cdot log(n))O(n\backslash cdot\; log(n))$

空间复杂度: 相比于之前,这里多了前缀和数组,因为前缀和的长度和原数组长度相关,所以空间复杂度为$O(n)O(n)$