209 - Minimum Size Subarray Sum

Minimum Size Subarray Sum

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

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

click to show more practice.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Hide Tags

Array Two Pointers Binary Search

Hide Similar Problems

(H) Minimum Window Substring

 

没想到合适的方法，参考别人的思路做出来的。

线性复杂度的方法是，先从头求和，直到和大于s才停下来，

然后平移，且移动起点以求缩小长度来满足和大于s，

直到移到最末尾，且不能再收缩为止，这期间的最小长度即是结果。

 

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int rst=0;
        int sz=nums.size();
        if(sz)
        {
            int idx1=0, idx2=0;
            int sum=nums[0];

            //keep adding untill sum >= s
            while(idx2<sz && sum<s)
                sum += nums[++idx2];

            //if s is even bigger than all sum, return 0
            if(idx2 == sz)
                return 0;

            //now we have a subset length to make sum >= s
            rst = idx2+1;

            //let's check for smaller length:
            int len = rst;
            while(idx2<sz)
            {
                //move idx2 --> right by 1 element, add next element to sum,
                if(idx2<sz-1)
                {
                    sum += nums[idx2+1];
                    len++;
                }
                idx2++;

                //then keep moving idx1 one by one to check if (sum - nums[idx1]) > s
                while((sum-nums[idx1])>=s)
                {
                    sum -= nums[idx1++];
                    len--;
                }
                //untile smaller, and updating rst at the same time.
                rst = (len<rst)?len:rst;               
           }
        }
        return rst;
    }
};

4 ms.

 

关于 nlgn 的解法，也就是折半查找的方法，稍后再写。