[算法学习篇]-滑动窗口算法（javascript [算法学习篇]-滑动窗口算法（

滑动窗口算法：
字面意思，大家都见过窗户吧，开关窗户也都会吧（废话×）
这里的滑动窗口算法的窗口分为固定的和不固定的，固定的就是生活中见到的那种窗口，想象一下有个大窗口，然后滑动的是纱窗，此处的纱窗就是固定的滑动窗口，要是不固定的呢就需要自己想象了这个纱窗是可伸缩的。
网上随便找的一张图，可以感受一下：

文章图片

其中后面的大窗口就是要遍历的对象，纱窗分左边框和右边框，用来在大窗口寻找符合条件的目标对象。注意：对于固定窗口的话就没必要使用左边框了，因为固定窗口的话固定大小若为k，直接用右边框减去k就等于左边框了。
看一下一道滑动窗口的算法题来感受一下（固定窗口）：语言：JavaScript
1、自创题（很简单，可以做着玩玩）：给定一组数组，遍历数组，每三个算作一个子串，算出每个组合的子串的和，
进阶：算出每个组合的子串的和后找到其中的最大值。
输入：[-3，3，5，1，3，7，4]
输出：[5，9，9，11，14]
进阶输出：14
解释：①-3+3+5=5 ②3+5+1=9 ③5+1+3=9 ④1+3+7=11 ⑤3+7+4=14
下面展示最笨的方法hhh（后续再想优化方案）：

function temp(s) { let left = 0,right = 2; // 定义滑动窗口的左右边框 let sumArr = []; // 每滑动一次求到的和放到新的数组里 let n = s.length; // 数组的长度赋值给一个新的变量 if (n <= 2) { //因为固定窗口是3，若数组里值的数量小于3则没必要继续做 return s; // 直接返回数组 } while (right < n) { //遍历条件，当右边框大于n时停止遍历，控制次数 let sum = 0; // sum用于记录每组子串的和，因为要重复利用所以要置0 for (let i = left; i <= right; i++) { // 二层循环用于遍历每个[left,right]子串 sum += s[i]; //每三个一组的子串的和 } sumArr.push(sum); // 得到一组的和就放到新的数组里 right++; // 算完一组子串后，窗口开始往右滑动 left++; } const max = Math.max(...sumArr); // 获取一组数组的最大值 return sumArr; //进阶：求数组里数字的最大值：Math.max(…sumArr); } }

知识点：

① length()方法返回数组或字符串的长度 ② push() 方法将一个或多个元素添加到数组的末尾，并返回该数组的新长度 ③ Math.max() 函数返回一组数中的最大值

知识点就简单罗列一下，具体的可以去MDN学习。
2、力扣网的题=》无重复字符的最长子串（链接在此，有兴趣的可以去做做看）：
https://leetcode-cn.com/probl...
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

下面简单写上三种写法：
方法一：set/map(差不多，用set吧，map没必要)

function temp(s) { let n = s.length; let set = new Set(); // 定义一个set let left = 0, right = 0, maxLen = 0; // 左右边框，最大值 if (n < =1) {// 如果s小于等于1，则没必要判断，直接输出长度 return n; } while (right < n) { if (!set.has(s[right])) {// 判断set里是否包含s里的元素 set.add(s[right]); // 不包含则加入set maxLen = Math.max(maxLen, right - left + 1); //然后计算无重复最长子串的长度，因为是窗口所以长度是right-left+1（右边框 – 左边框 + 1） right++; // 没有重复的元素时右边框继续往右滑动 } else { set.delete(s[left]); // 如果set里有重复的值，就从左边框开始删掉 left++; // 滑动左边框 } } return maxLen; };

知识点：

① 新建set：let set = new Set(); 注意set里的元素是不重复的 ② set里的方法：has，add，delete等 ③ Math.max() 函数返回一组数中的最大值

图解（简陋版）：

文章图片

图解（进阶版）：

文章图片

方法二：数组法（这相当于固定窗口了，一次一个）

function temp (s) { let arr = [],max = 0; if (s.length <=1) { return s.length; } for (let i = 0; i < s.length; i++) { let index = arr.indexOf(s[i]); // 查看数组里是否包含s里的元素 if (index !== -1) {// index等于-1就是不包含，此处判断包含 arr.splice(0, index + 1); // 删掉数组里从0到重复值 } else { arr.push(s[i]); //或arr.push(s.charAt(i)); // 没有重复的则把元素放到数组里 max = Math.max(max, arr.length); // 判断长度 } } return max; };

知识点：

① indexOf：查看数组里是否包含某元素，存在返回其下标，不存在则返回-1 ② splice(start,count,item)：删除数组里的元素，从0开start开始删除count个元素，item可选，具体用法见MDN。 ③ push()：往数组末尾添加元素 ④ charAt(index)：从字符串中返回指定坐标的值

图解：（橙色是输入的数组，蓝色是新建的数组）

文章图片

方法三：下标法

function temp(s) { let index = 0,max = 0; if (s.length <= 1) { return s.length; } for (let let = 0, right = 0; right < s.length; right++) { // 遍历字符串 index = s.substring(left, right).indexOf(s[right]); //判断字符串里是否有重复元素 if (index !== -1) { left = left + index + 1; // 有重复元素，滑动窗口，直接跳到重复元素下一个索引，left+重复元素下标+1 } else { //没有重复元素，比较max和右-左+1 max = Math.max(max, right - left + 1); } } return max; }

知识点：

① substring(start,end)：字符串里的方法,截取从[start,end)的子串注意：index那一步骤，indexOf是在substring的基础上寻找的，所以返回的索引也是从 substring的字符串里开始算的。这影响到left=left+index+1那一步骤。有重复元素的话就直接左边框滑动到重复元素的下一个索引就好。

图解：

文章图片

参考文章：
https://leetcode-cn.com/probl...
做题的时候参考了上述文章，加上了自己的理解，有写的不对的地方还望指正，关于知识点部分详情可以去看MDN的官方文档，这边先放上一些吧（String，Array，Math的方法）
【String】https://developer.mozilla.org...
【[算法学习篇]-滑动窗口算法（javascript】【Math】https://developer.mozilla.org...
【Array】https://developer.mozilla.org...