算法训练营第2天｜209.长度最小的子数组、59.螺旋矩阵II

/**
 * 暴力解法
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
  // 定义一个足够大的长度
  let result = 999999999999
  let subLength = 0; // 子数组长度
  for (let i = 0; i < nums.length; i++) {
    let sum = 0 // 每次从头开始计时
    for (let j = i; j < nums.length; j++) {
      sum = sum + nums[j] // 计算和
      if (sum >= target) { // 如果大于等于目标值
        subLength = j - i + 1 // 得到数组长度
        result = result < subLength ? result : subLength // 和之前的长度做比较，谁短就是谁
        break  // 找符合条件最短的子序列，所以一旦符合条件就break，没必要再加sum了
      }
    }
  }
  // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
  return result === 999999999999 ? 0 : result
};

/**
 * 滑动窗口解法
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
  // 定义一个长度结果
  let res = 999999999999
  // 子数组的长度
  let subLen = 0
  // 定义一个窗口初始下标
  let i = 0
  // 和
  let sum = 0
  for (let j = 0; j < nums.length; j++) {
    // 相对于暴力解法，这里的sum在相加之后不用break
    sum = sum + nums[j]
    // 一旦大于等于目标值，就检查最小长度
    // 这里一定要用 while，因为可能会出现[1,1,1,1,100]，target 为 100
    // 滑动窗口为[1,1,1,1,100]时，当 j 移动到 100 时，只会判断一次
    // 如果i不继续往右移动，得出的 length = 5， 实际上是 2，[1,100]
    while (sum >= target) {
      // 得到子数组长度
      subLen = j - i + 1
      // 检查最小长度
      res = res < subLen ? res : subLen
      // 减去初始位置的值，直到让sum小于目标值
      sum = sum - nums[i]
      // 并且移动窗口起始位置，
      i++
    }
  }
  return res === 999999999999 ? 0 : res
};

const generateMatrix = function(n) {
  //  定义矩阵，用 0 填满
  let res = new Array(n).fill(0).map(() => new Array(n).fill(0))
  // 整体要循环的次数，n= 3，则转一圈就行，中间的特殊处理，n=4，则要转两圈
  let loop = Math.floor(n/2)
  // 如果n 为奇数，则需要特殊处理最中间的值，它的坐标就是 n/2
  let mid = Math.floor(n/2)
  // 定义起始值，[i,j]，startX在二维数组为为 i 的起始值，但在坐标轴上为 Y轴，startY为 j 的值
  let startX = 0
  let startY = 0
  // 偏移量，每转一圈，就需要加 1，就可能转内圈
  let offset = 1
  // 填充数字
  let count = 1
  // loop > 0 才转
  while (loop--) {
    // i坐标
    let row = startX
    // j 坐标
    let col = startY
    // 左上到右上（左闭右开）
    // n-offset 就是为了左闭右开
    // 假设 n = 5， 则 n-offset = 4，只需要循环1,2,3,4。5 则留给其他边处理
    // 不停推动 col，也就是 j 向右移动
    for (;col < n-offset; col ++) {
      res[row][col] = count ++
    }

    // 右上到右下（左闭右开）
    // 不停推动 row，也就是 i 向下移动
    for (;row < n-offset;row ++) {
      res[row][col] = count ++
    }

    // 右下到左下（左闭右开）
    // 不停推动 col，也就是 j 向左移动
    for (;col> startY; col --) {
      res[row][col] = count ++
    }
    // 左下到左上
    // // 不停推动 row，也就是 i 向上移动
    for (;row > startX; row --) {
      res[row][col] = count ++
    }
    // 进入第二圈的时候，起始坐标[i,j]都需要+1，才能进内圈
    startX ++
    startY ++
    // 偏移量也需要+1，保证左闭右开
    offset ++
  }
  // 特殊处理奇数 n 的情况，手动更新最中间的值
  if (n%2 === 1) {
    res[mid][mid] = count
  }

  return res

};