关于算法:算法学习篇滑动窗口算法javascript

4次阅读

共计 3064 个字符，预计需要花费 8 分钟才能阅读完成。

字面意思，大家都见过窗户吧，开关窗户也都会吧（废话×）
这里的滑动窗口算法的窗口分为固定的和不固定的，固定的就是生存中见到的那种窗口，设想一下有个大窗口，而后滑动的是纱窗，此处的纱窗就是固定的滑动窗口，要是不固定的呢就须要本人设想了这个纱窗是可伸缩的。
网上轻易找的一张图，能够感受一下：

其中前面的大窗口就是要遍历的对象，纱窗分左边框和左边框，用来在大窗口寻找符合条件的指标对象。留神：对于固定窗口的话就没必要应用左边框了，因为固定窗口的话固定大小若为 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…

【Math】https://developer.mozilla.org…

【Array】https://developer.mozilla.org…

正文完