209. 长度最小的子数组

暴力

class Solution {
    
    public int minSubArrayLen(int target, int[] nums) {
    
        int len=nums.length;
        int min=Integer.MAX_VALUE;
        for(int i=0;i<len;i++){
    //start
            int sum=0;
            for(int j=i;j<len;j++){
    // 从[i,j]相加
                sum+=nums[j];
                if(sum>=target){
    
                    min=Math.min(min,j-i+1);
                    break;
                }
            }
        }
        //还要有min=0的情况，即不存在符合这样长度的数组
        return min==Integer.MAX_VALUE?0:min;
    }
}

前缀和、二分查找

• 前缀和：sum[i], 前i个元素的和
  num数组里的数都是正数，所以sum为递增的，可用二分法查找
• sum[j]-sum[i]: 从前j个减去前i个 也就是第i+1个到第j个 索引为[i,j-1]
  即找到sum[j]-sum[i]>=s的值
  即找到sum[i]+target<=sum[j]的j值 其长度为j-i+1
• 步骤
  for循环对每一个i求出aim=sum[i]+target
  用二分法遍历sum数组找到 大于aim的sum值
• 4 [1,4,4]
  sum[1]+4=5,二分查找sum[0,1,5,9]找到后边[5，9]中大于等于5的数，长度更新为2
  sum[2]+4=9, 3-3+1=1

class Solution {
    
    public int minSubArrayLen(int target, int[] nums) {
    
        int min=Integer.MAX_VALUE;
        int len=nums.length;
        int[] sum=new int[len+1];//前0个，前len个的和
        sum[0]=0;
        //计算sum数组
        for(int i=1;i<=len;i++){
    
            sum[i]=sum[i-1]+nums[i-1];//前i-1个的和+ 第i个的和=前i个的和
        } 
        
        //遍历每一个sum[i]即以i为开头，找大于sum[i]+target的数
        //如何找——用二分法
        for(int i=1;i<=len;i++){
    
            int aim=sum[i-1]+target;//前i-1个元素
            int j=binfind(sum,0,len,aim); 
            //即没有找到满足大于 sum[i]+target 的j的值
            // if(j==-1){
    
            // j=0;
            // }
            if(j>0&&j<=len){
    
                min=Math.min(min,j-i+1);
            }

        }
        //还要有min=0的情况，即不存在符合这样长度的数组
        return min==Integer.MAX_VALUE?0:min;
        

    }

    //用二分法找到一个>=target的值
    int binfind(int[]nums,int left,int right,int target){
    
        while(left<right){
    
            int mid=(left+right)/2;
            //通过target进行二分查找
            if(nums[mid]<target){
    
                left=mid+1;
            }
            else if(nums[mid]>=target){
    
                right=mid;
            }
        }
        //最终mid要大于等于target,如果返回-1即找不到>=target的数
        return nums[left]>=target?left:-1;
    }
}