【LeetCode】209. 长度最小的子数组（中等）——代码随想录算法训练营Day02

题解1（失败）：暴力法

思路：首先想到可以利用双重 for 循环来求解，i 遍历记录新数组的左边界，j 变量记录右边界。

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
  let res = 0; // 结果
  for (let i = 0; i < nums.length; i++) {
    let sum = 0; // 记录子数组元素和
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      if (sum >= target) {
        let temp = j - i + 1; // 计算子数组长度
        if (temp < res || res === 0) {
          res = temp;
        }
        break;
      }
    }
  }
  return res;
};

分析：此解法使用了双层循环，数组中的每一个元素都要和其后续所有元素来逐个比较，平白增加了时间消耗。时间复杂度为 O(n2)，空间复杂度为 O(1)。

不出意外提交失败了，超出时间限制，要通过本题需要寻找时间复杂度低于 O(n2) 的解法。

题解2：滑动窗口

思路：可以使用滑动窗口的方法把双层 for 循环改为1个 for 循环。for 循环的循环变量为终止位置，循环中计算滑动窗口中元素和的大小，当其大于等于目标值时，向后移动起始位置，并记录下窗口大小，最后选取最小的窗口结果为最终结果。

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
  let res = 0; // 最小长度
  let i = 0; // 起始位置
  let sum = 0; // 当前窗口内元素和
  for (let j = 0; j < nums.length; j++) {
    sum += nums[j]; // 计算窗口内的元素和
    // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
    while (sum >= target) {
      let temp = j - i + 1; // 当前长度
      if (temp < res || res === 0) {
        res = temp; // 更新最小长度
      }
      sum -= nums[i++]; // 移动起始位置
    }
  }
  return res;
};

分析：使用了滑动窗口，起始位置 i 和 终止 位置 j 都只遍历了一遍数组，时间复杂度为 O(n)，空间复杂度为 O(1)。

收获

理解了滑动窗口的原理，使用滑动窗口时遍历的是滑动窗口的终止位置，当满足某些条件时再向后移动起始位置，这样就可以将暴力法的两层循环优化为一层循环。