首页 > the7 > 剑指 Offer II 008. 和大于等于 target 的最短子数组


剑指 Offer II 008. 和大于等于 target 的最短子数组


在这里插入图片描述

暴力查找的方法:
(采用js)

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    var a = [];
    for(let i=0;i<nums.length;i++){
        let start=i+1,sum=nums[i],count=1;
        while(start<=nums.length){
            if(sum>=target){
                a.push(count);
                break;
            }
            else if(sum<target&&start<=nums.length){
                sum+=nums[start];
                start++;
                count++;
            }
        }
    }
    if(a.length==0){
        return 0;
    }
    a.sort((a,b)=>a-b);
    return a[0];
};
  • 思路:让每一个元素都当首元素,然后遍历后面的元素,如果找到第一个数字让首元素到这个数字之间所有的数字相加大于等于target就break跳出循环(因为要找长度最小的子数组,所以找到就结束),然后将下一个元素作为首元素继续遍历。开辟一个数组将每种情况的长度存储在数组里面,然后递增排序,输出最小的值

代码优化:

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    var ml = Number.MAX_VALUE;
    for(let i=0;i<nums.length;i++){
        let start=i+1,sum=nums[i],count=1;
        while(start<=nums.length){
            if(sum>=target){
                ml=Math.min(ml,count);
                break;
            }
            else if(sum<target&&start<=nums.length){
                sum+=nums[start];
                start++;
                count++;
            }
        }
    }
    return ml==Number.MAX_VALUE?0:ml;
};
  • 优化:不使用数组进行存放,设置一个变量ml存放最小长度,当满足条件的时候就比较当前和上一次的ml谁大谁小,将小的值赋值给ml,最后输出ml,这样减少内存的消耗

将代码简化

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    var ml = Number.MAX_VALUE;
    for(let i=0;i<nums.length;i++){
        let start=i+1,sum=nums[i],count=1;
        while(start<=nums.length&&sum<target){
            sum+=nums[start];
            start++;
            count++;
        }
        if(sum>=target)
            ml=Math.min(ml,count);
    }
    return ml==Number.MAX_VALUE?0:ml;
};

使用滑动窗口的方法(时间复杂度和空间复杂度均减小)

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
  let left = 0,
    sum = 0;
  let minLength = Number.MAX_VALUE;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    // sum>=target 已经是找到了可行解了
    while (left <= right && sum >= target) {
      //  移动左边界,在可行解里面寻找最优解
      minLength = Math.min(minLength, right - left + 1);
      sum -= nums[left++];
    }
  }
  return minLength == Number.MAX_VALUE ? 0 : minLength;
};

思路:先将左右窗口都设置为首元素,让窗口向右走,所以设置循环让右窗口不断++。使用sum值记录当前窗口内所有元素的值,每次在右窗口滑动后还要判断,sum是否>=target,如果是就将此时的窗口长度记录下来,然后让右窗口向右移动,然后判断移动之后sum值是否还>=target如果是将此时的窗口长度记录下来(因为左窗口向右移动了,窗口长度变小了,所以当前满足情况的长度为最小的长度),因为可能要不断的右移左窗口,所以这里设置循环(注意一个循环条件是左窗口的值不能大于右窗口)。在循环题里面,首先将满足sum>=target的值与前一个值相比最小的值记录下来,然后右移左窗口,记录sum值进行循环判断。不满足条件就退出循环继续右移右窗口。最后得到长度最小的值。