共计 1956 个字符，预计需要花费 5 分钟才能阅读完成。
一、前言
《JavaScript 刷 LeetCode 拿 offer- 双指针技巧》中，简略地介绍了双指针技巧相比拟单指针的长处，以及联合 Easy 难度的题目带大家进一步理解双指针的利用。
进入 Medium 难度之后，解题的关键在于如何结构双指针以及确定指针挪动的规定，解题办法能够演绎为以下两类：
- 滑动窗口算法（Sliding Window Algorithm）;
- 对数组进行预处理（如：排序，前缀和等等），再利用双指针遍历;
这两种办法都能够将双循环问题转化为单循环问题，从而无效地升高算法的工夫复杂度。本篇次要介绍滑动窗口算法以及相干题型的解题思路，第二类题型会放在下一篇中解说。
滑动窗口算法具体的表现形式为：左右指针始终保护一个满足条件的窗口值，右指针负责向前遍历，当窗口值不满足条件时，将左指针指向的元素移出窗口，同时向前挪动左指针。
上面，结合实际的题目来了解如何应用滑动窗口算法。
二、567. 字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否蕴含 s1 的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。
本道题目实际上能够转化为是否能找出满足以下条件的 s2 字符串的子串：
- 该子串的长度和 s1 字符串的长度相等；
- 该子串中蕴含的字符以及对应的数量和 s1 字符串雷同；
那么联合滑动窗口算法，须要保护一个长度为 s1 字符串长度的窗口，并且窗口中的字符以及相应的数量与 s1 雷同。
字符数量通过 HashTable 来保护，在 JavaScript 语言中能够采纳 Map 数据结构。
三、904. 水果成篮
在一排树中，第 i 棵树产生 tree[i] 型的水果。你能够从你抉择的任何树开始，而后反复执行以下步骤：1、把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。2、挪动到以后树右侧的下一棵树。如果左边没有树，就停下来。请留神，在抉择一颗树后，你没有任何抉择：你必须执行步骤 1，而后执行步骤 2，而后返回步骤 1，而后执行步骤 2，依此类推，直至进行。你有两个篮子，每个篮子能够携带任何数量的水果，但你心愿每个篮子只携带一种类型的水果。用这个程序你能收集的水果总量是多少？
这道题很显著合乎滑动窗口算法的特色：保护一个至少有两种水果的窗口。
当窗口中呈现第三种水果时，须要从窗口的右边顺次移除果树，保障以后窗口只含有两种水果，这里能够采纳 HashTable 记录同一类型果树最初呈现的坐标来优化工夫复杂度。
最初，在窗口挪动的过程中，计算相应的水果总量即可。参考视频：传送门
四、3. 无反复字符的最长子串
给定一个字符串，请你找出其中不含有反复字符的 最长子串 的长度。
这道题目与上一道《904. 水果成篮》的解题思路如出一撤：
- 保护一个不含反复字符的窗口；
- 当窗口不满足条件时，从窗口右侧顺次移除字符，确保窗口再次满足条件，同样能够采纳 HashTable 记录雷同字符最初呈现的下标来优化工夫复杂度；
五、713. 乘积小于 K 的子数组
给定一个正整数数组 nums。找出该数组内乘积小于 k 的间断的子数组的个数。
本题须要保护一个乘积小于 k 的窗口，与上述题目相比，本题不须要太多技巧去计算无效的窗口值，它的难点在于 满足乘积的数组的长度正好是以后不重复子数组的数量。
六、845. 数组中的最长山脉
咱们把数组 A 中合乎下列属性的任意间断子数组 B 称为“山脉”：1、B.length >= 3；2、存在 0 < i < B.length – 1 使得 B[0] < B[1] < … B[i-1] < B[i] > B[i+1] > … > B[B.length – 1]（留神：B 能够是 A 的任意子数组，包含整个数组 A。）给出一个整数数组 A，返回最长“山脉”的长度。如果不含有“山脉”则返回
0。
以本题为例，感受一下奢侈解法与滑动窗口算法之间的差距。
奢侈解法的思路：顺次以数组中的元素为“峰顶”，如果满足“山脉”的条件，那么统计长度。
上述代码的工夫复杂度为 O(n^2)。
本题利用滑动窗口算法的难点在于如何确定以后窗口中的无效“山脉”状态：
- 窗口挪动的过程中，须要采纳两个变量来记录以后窗口中蕴含的序列的枯燥性；
- 窗口挪动过程中遇到递增序列时，如果此时窗口中曾经蕴含递加序列，那么须要向前挪动左指针，从新形成“山脉”；
- 窗口挪动过程中遇到递加序列时，如果此时窗口中不蕴含递增序列，同样须要向前挪动左指针，从新形成“山脉”；
利用滑动窗口算法胜利地将工夫复杂度升高为 O(n)。
写在最初
算法作为计算机的基础学科，用 JavaScript 刷，一点也不丢人 ε =ε=ε=┏(゜ロ゜;)┛。
本系列文章会别离给出一种算法的 3 种难度的总结篇（简略难度，中等难度以及艰难难度）。在简略难度中，会介绍该算法的基本知识与实现，另外两个难度，着重解说解题的思路。
如果本文对您有所帮忙，能够点赞或者关注来激励博主
