Table of contents

• 引言
• 滑动窗口介绍
• 使用滑动窗口解题
• 代码实现

引言

leetcode 上有不少最长/最短/ 子串/ 子序列/子数组 的问题，此类问题，虽然都可以通过暴力循环方式解决，但不能满足对与时间复杂度的要求，所以也无展开讨论的意义。本篇文章记录一下如何利用双指针或者滑动窗口来解决此类型问题。

滑动窗口介绍

滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

滑动窗口和双向指针都是为了简化过多的循环的。

滑动窗口也可以理解为双指针法的一种！只不过这种解法更像是一个窗口的移动， 所以叫做滑动窗口更适合一些。

使用滑动窗口解题

以 leetcode207 题为例子，下面看这道题：

先使用第一个用例，画图解释

step1, 定义一个函数，函数参数是一个target 与一个数组，并声明左右两个指针，初始值为0

function minSubArrayLen(target: number, nums: number[]): number {
  let left:number = 0;   
  let right:number = 0;
  let sum:number = 0; // 存储相加之和  
  let res:number = 0; // 存储结果result
}

step2, 指针定义好后，现在让指针动起来

function minSubArrayLen(target: number, nums: number[]): number {
  let left:number = 0;  
  let right:number = 0;
  let sum:number = 0; // 存储相加之和  
  let res:number = 0; // 存储结果result
  while (right < nums.length) {
    ...
    rigth ++
  }
}

step3，我们需要得到第一个满足条件的值，让连续子数组的和大于7。当 right 指向下标3时，得到第一个大于等于7的值

while (right < nums.length) {
  sum += nums[right]
  ...
  rigth ++
}

此时，right 指针停止移动，left指针开始移动，

所以此处为left 指针的移动的触发条件，即当 sum >=7 时，left ++，而此时 sum 需要重新计算,

此处 res 的赋值的逻辑是这样的，当right -left 的值小于 res时，就使用 right -left , 否则继续使用当前的res 值

while (right < nums.length) {
  sum += nums[right]
  if (sum >= target) {
    sum -= nums[left]
    res = Math.min(res, right - left + 1)
    left++
  } 
  ...
  rigth ++
}

step4, left向后移动一位后，sum 和为6，小于7，此时 right ++

while (right < nums.length) {
  sum += nums[right]
  if (sum >= target) {
    sum -= nums[left]
    res = Math.min(res, right - left + 1)
    left++
  } 
  right ++
  return res
}

这里有一个坑，比如数组为 [1,1,1,1,1, 100] , 假如按上面代码执行，left 第一次左移后，就停止运行了，此时length 为 5，然而希望输出的是2，

所以这里需要再加一个while 循环

while (right < nums.length) {
  sum += nums[right]
  if (sum >= target) {
    while (sum - nums[left] >= target) {
    	sum -= nums[left]
     	left++
    }
    res = Math.min(res, right - left + 1)  
  } 
  right++
  return res
}

step5，最后需要考虑的是， res 的初始值和最后的返回值

通常我们习惯将数字类型的变量初始为 0，但逻辑中有一条比较是 Math.min(res, right - left + 1) , 所以为了复用这里的逻辑，我们可以将 sum 的值设为 nums.length +1

返回的时候，将 res 和nums.lenght +1 做比较，如果相等，说明res 从未赋值过，返回0 即可，如果不相等，则返回res

代码实现

最后来看代码实现：

function minSubArrayLen(target: number, nums: number[]): number { 
  let res: number = nums.length + 1;
  let left = 0;
  let right = 0;
  let sum = 0;
  while (right < nums.length) {
    sum += nums[right]
    if ( sum >= target) {
        // res = Math.min(res, right - left + 1);
        while (sum - nums[left] >= target) {
            sum -= nums[left++];
        }
        res = Math.min(res, right - left + 1);
        // res = right - left < res ?right-left : res
    }
    right ++
    console.log(res)
  }
  return res === nums.length + 1 ? 0 : res;
};