初学者LeetCode-(209)长度最小的子数组三种解法

1.题目

给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。 示例 1: 输入:target = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数组 [4,3] 是该条件下的长度最小的子数组。 示例 2: 输入:target = 4, nums = [1,4,4] 输出:1 示例 3: 输入:target = 11, nums = [1,1,1,1,1,1,1,1] 输出:0

2.三种解法

(1)暴力解法

这道题可以从第一位(小于目标值)开始一直依次向后加,直到加到大于目标值,开始计算开始到结束的距离,然后进行第二个数依次向后加的行为,比较最小距离,因此使用双重循环,实现查找最小距离的方式,当查找到第一次出现大于目标值的距离时,后续可以不用在查找,进入下一次的循环查找,可以加快运行速度。代码展示:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int min=Integer.MAX_VALUE;
        for(int i=0;i<=nums.length-1;i++){
             int sum=0;
            for(int j=i;j<=nums.length-1;j++){
               sum+=nums[j];
               if(sum>=target){
                   min=Math.min(min,j-i+1);
                   break;
               }            
            }
        }
        return min==Integer.MAX_VALUE?0:min;
    }
}

(2) 双指针解法

即使使用暴力可以运行出结果,但运行速度还是有点慢,使用双指针可以加快运行速度,双指针的解题思路是:首先定义两个指针,将j作为首指针看待,如例1数组为[2,3,1,2,4,3]所看,先将2放入,对比是否大于目标值,不大于就继续向后进行累加,当累加大于目标值时,进行最小距离的赋值,这时总和减去i代表的尾指针,再进行判断,若小于目标值进行累加,若加上后一位和大于目标值,再进行减去尾指针的操作,当出现距离小于之前判断的值进行重新最小值赋值。代码展示:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
      int i=0,j=0,sum=0;
      int min=Integer.MAX_VALUE;
      while(j<nums.length){
          sum+=nums[j++];
          while(sum>=target){
              min=Math.min(min,j-i);
              sum-=nums[i++];
          }
      }
      return min==Integer.MAX_VALUE?0:min;
    }
}

(3) 二分查找

此题还可以使用二分查找方法,给一个全新的数组进行存储sum值,要考虑长度匹配问题,例如sum[1]=nums[0]、sum[2]=nums[0]+nums[1],为了节省时间直接在程序中调用二分查找语句,但因为底层代码问题,需要判断k是否小于0,若小于0进行按位取反,是为了保证左边界和右边界在数组内,然后进行最小值比较赋值,代码展示:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
       int[] sum=new int[nums.length+1];
       int min=Integer.MAX_VALUE; 
       for(int i=1;i<=nums.length;i++){
            sum[i]=sum[i-1]+nums[i-1];
       }
       
       for(int j=0;j<sum.length;j++){

           int index=target+sum[j];
           int k=Arrays.binarySearch(sum,index);

           if(k<0){
               k = ~k;
           }
           if(k<=nums.length){
                min=Math.min(k-j,min);
           }
     }

       return min==Integer.MAX_VALUE?0:min;
    }
}
经验分享 程序员 微信小程序 职场和发展