leetcode---长度最小的数组(JavaScript解法----滑动窗口)

刺骨的言语ヽ痛彻心扉 2023-02-21 06:27 8阅读 0赞

#### 一、题目描述 ####

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

#### 二、示例 ####

![在这里插入图片描述][20200629110956266.png]

#### 三、思路分析 ####

这个题目我们拿到之后分析，他要一个连续的区间，是一个典型的双指针问题，我们使用快慢指针以及两层循环实现。  
连续子数组可以表示为 \[i,j\]：从第 i 项到第 j 项  
如果 \[i,j\] 的 sum >= s ，如果扩张窗口，条件依然满足，但更背离“最小长度”的要求  
所以选择收缩窗口，i 右移，直到条件不再满足，所以这里是一个循环  
在循环中，将窗口长度和全局的最小比较  
如果窗口不再 sum >= s ，此时应该扩张窗口，j 右移，直到条件重新满足  
移动窗口的套路

*  扩张窗口：找可行解，找到了就不再扩张
 *  收缩窗口：在长度上优化该可行解，直到条件被破坏
 *  寻找下一个可行解，然后再优化……  
    我们可以画图来理解，就是先一次循环依次放到sum中去和s进行判断，如果大于的话，后指针不动，前指针往前i++，记录当前窗口的长度，知道不满足sum>=s这个条件，进行后指针j++，两个循环嵌套即可。

#### 四、代码展示 ####

/** * @param {number} s * @param {number[]} nums * @return {number} */
    // var minSubArrayLen = function(s, nums) { 
    // var i = 0;
    // var sum = 0
    // var minLen = Infinity
    // for(let j = 0 ; j < nums.length ; j++){ 
    // sum+=nums[j]
    // while(sum>=s){ 
    // minLen = Math.min(minLen,j-i+1)
    // sum -= nums[i]
    // i++
    // }
    // }
    // return minLen === Infinity ? 0 : minLen
    // };
    
    
    const minSubArrayLen = (s, nums) => { 
      let minLen = Infinity;
      let i = 0;
      let j = 0;
      let sum = 0;
      while (j < nums.length) {    // 主旋律是扩张，找可行解
        sum += nums[j];
        while (sum >= s) {         // 间歇性收缩，优化可行解
          minLen = Math.min(minLen, j - i + 1);
          sum -= nums[i];
          i++;
        }
        j++;
      }
      return minLen === Infinity ? 0 : minLen; // 从未找到可行解，返回0
    };

#### 五、结果 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70]

[20200629110956266.png]: https://img-blog.csdnimg.cn/20200629110956266.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200629111034652.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4,size_16,color_FFFFFF,t_70