滑动窗口(四)——leetcode No.209. Minimu

题目:

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.

Example:

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.
Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

分析:

这个题如果只考虑O(n)的解法,就是道easy难度的题目,因为就变成了典型的滑动窗口,设置两个变量end,start,每次先滑动窗口的end,直到sum>=s为止,然后滑动start使得sum小于s为止,记录此时end与start差,维护最小长度,继续滑动窗口直到end到达边界.

显然复杂度为O(n),因为end变量是一直在动的,而start又受制于end变化,外层仅有end的遍历.

考虑O(nlogn)的复杂度,由于有logn,一般是用二分法,接下来就是如何二分的问题,我们可以考虑用连续值sum来判断,代码写得很详细了,可以看代码.

代码:

public class Solution{
    public int minSubArrayLen(int s,int [] nums){
        return solveNlogN(s,nums);
    }
    private int solveNlogN(int s,int [] nums){
        int [] sums = new int[nums.length+1];
        // init the sums
        for(int i=1;i<sums.length;i++){
            sums[i]=sums[i-1]+nums[i-1];
        }
        int minLen = Integer.MAX_VALUE;
        //二分查找序列
        for(int i=0;i<sums.length;i++){
            int end=binarySearch(i+1,sums.length-1,sums[i]+s,sums);
            if(end==sums.length){
                break;
            }
            minLen=Math.min(minLen,end-i);
        }
        return minLen==Integer.MAX_VALUE?0:minLen;
    }
    private int binarySearch(int lo,int hi,int key,int [] sums){
        while(lo<=hi){
            int mid = (lo+hi)/2;
            if(sums[mid]>=key){
                hi=mid-1;
            }
            else {
                lo=mid+1;
            }
        }
        return lo;
    }
    private int solveN(int s,int [] nums){
        int start=0,end=0,sum=0,minLen=Integer.MAX_VALUE;
        while(end<nums.length){
            while(end<nums.length&&sum<s){
                sum+=nums[end++];
            }
            if(sum<s)
                break;
            while(start<end&&sum>=s){
                sum-=nums[start++];
            }
            minLen=Math.min(minLen,end-start+1);
        }
        return minLen==Integer.MAX_VALUE?0:minLen;
    }

}