题目描述

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

题意：求一个正数数组的和大于等于$s$的最短连续子数组长度。

样例

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

算法1

(前缀和+二分) $O(nlogn)$

题解1:考虑到所有元素都是正数，那么说明如果存在长度为$k（k < n）$的连续子数组的和大于$s$，那么一定存在长度为$k+1$的连续子数组的和大于$s$。那么我们可以考虑使用二分找到这个最小的$k$。二分查找每个可能的$k$，遍历一边数组，判断是否存在长度为$k$的连续子数组的和大于$s$，可以使用前缀和来辅助计算子数组的和。时间复杂度：二分查找$O(logn)$，判断是否存在$O(n)$，总的时间复杂度为$O (nlogn)$

C++ 代码

    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        if(n == 0) return 0;
        vector<int> preSum(n + 1,0);
        for(int i = 0; i < n ; i++)
            preSum[i + 1] = preSum[i] + nums[i];
        if(preSum[n] < s) return 0;//不存在解
        int left = 1, right = n;
        while(left < right)
        {
            int mid = (left + right) / 2;
            if(check(s,mid,nums,preSum)) right = mid;
            else left = mid + 1;
        }
        return left;
    }
    bool check(int s,int k,vector<int> nums,vector<int> preSum)
    {
        for(int i = 0 ; i <= nums.size() - k ; i ++)
            if(preSum[i + k] - preSum[i] >= s )
                return true;
        return false;
    }

算法2

双指针 $O(n)$

题解2:双指针算法。设置两个指针分别代表子数组的开头和结尾，如果该数组的和小于$s$，那么右指针后移；如果该数组的和大于等于$s$，那么比较最优解，同时左指针前移，直至当前数组和小于$s$。时间复杂度$O(n)$。

C++ 代码

    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        int cur_sum = nums[begin];//记录当前数组和
        int cur_min_len = INT_MAX;//记录当前最优解
        for(int begin = 0, end = 0; end < n;)
        {
            while(cur_sum >= s)
            {
                cur_min_len = min(cur_min_len,end - begin + 1);
                cur_sum -= nums[begin];//左指针后移
                begin ++;
            }
            end ++;//跳出循环后，当前值已经小于s了右指针后移。
            if(end < n) cur_sum += nums[end];
        }
        return (cur_min_len == INT_MAX)?0:cur_min_len;
    }