何谓滑动窗口
我们先看看leetcode是如何描述滑动窗口的
滑动窗口指的是这样一类问题的求解方法，在数组上通过双指针同向移动而解决的一类问题。其实这样的问题我们可以不必为它们专门命名一个名字，它们的解法其实是很自然的。
使用滑动窗口解决的问题通常是暴力解法的优化，掌握这一类问题最好的办法就是练习，然后思考清楚为什么可以使用滑动窗口。
可以看出，滑动窗口实际就是双指针同向移动的一种。可以想象，左右指针连接形成所谓的窗口，随着左右指针同时在数组中向后移动，就相当于窗口向后滑动，由此称为滑动窗口。值得注意的是，在指针向后的过程中，左右指针移动速度可以不同，所以窗口大小实际是不固定的。
滑动窗口经常适用于求解子串的题型中
leetcode真题
1. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 复制代码
这是道非常经典的滑动窗口，按照一般思路，我们很容易想到两层循环来解答，但是使用滑动我们可以做到只遍历一次。
var lengthOfLongestSubstring = function(s) { const Len = s.length let ans = 0 let left = 0 // 利用集合来存储窗口数据 const set = new Set() // i实际就是我们的右指针 for (let i = 0; i < Len; i++) { if (Len - left < ans) break const code = s[i] // 当新元素已经存在窗口中则收缩左指针 while(set.has(code)) { set.delete(s[left]) left++ } set.add(code) ans = Math.max(ans, i - left + 1) } return ans }; 复制代码
2. 字符串的排列
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串。
示例 1：
输入：s1 = "ab" s2 = "eidbaooo" 输出：true 解释：s2 包含 s1 的排列之一 ("ba"). 复制代码
同样是个求子串的题型，所以第一步可以先判断是否可以使用滑动窗口
var checkInclusion = function(s1, s2) { // 题目给出的一个特殊条件是全小写字母 // 所以可以很巧妙的运用长度为26的数组来记录字符出现次数 const cnt1 = new Array(26).fill(0) const cnt2 = new Array(26).fill(0) // 利用和字符a的字符差来放入和获取某个字符出现次数 const charCodeAtA = 'a'.charCodeAt() const s1n = s1.length; let ans = false; if (s2.length < s1.length) return false for (let i = 0; i < s1n; i++) { cnt1[s1[i].charCodeAt() - charCodeAtA]++ cnt2[s2[i].charCodeAt() - charCodeAtA]++ } if (cnt1.toString() === cnt2.toString()) return true for (let i = s1n, len = s2.length; i < len; i++) { // 滑动窗口 cnt2[s2[i].charCodeAt() - charCodeAtA]++ cnt2[s2[i-s1n].charCodeAt() - charCodeAtA]-- // 通过toString来对比是否相等 if (cnt1.toString() === cnt2.toString()) { ans = true break } } return ans }; 复制代码
3. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串。
示例 1:
输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。 复制代码
同样是寻找子串的题型，可以运用滑动窗口
var findAnagrams = function(s, p) { const PLen = p.length const countP = new Array(26).fill(0) const countS = new Array(26).fill(0) const charCodeA = 'a'.charCodeAt() const ans = [] let left = 0 for (let i = 0; i < PLen; i++) { countP[p[i].charCodeAt() - charCodeA]++ } // 滑动窗口 for (let i = 0, len = s.length; i < len; i++) { countS[s[i].charCodeAt() - charCodeA]++ if (i < PLen - 1) { continue } if (i >= PLen) { countS[s[left].charCodeAt() - charCodeA]-- left++ } // 利用26位数组来对比 if (countS.toString() === countP.toString()) { ans.push(left) } } return ans }; 复制代码
4. 乘积小于K的子数组
给定一个正整数数组 nums和整数 k。
请找出该数组内乘积小于 k 的连续的子数组的个数。
示例 1:
输入: nums = [10,5,2,6], k = 100 输出: 8 解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。 需要注意的是 [10,5,2] 并不是乘积小于100的子数组。 复制代码
var numSubarrayProductLessThanK = function(nums, k) { const Len = nums.length let count = 0 let left = 0 let multi = 1 // 滑动窗口 for (let i = 0; i < Len; i++) { multi = multi * nums[i] // 左指针右移动 while(multi >= k && left <= i) { multi = multi / nums[left++] } count += (i - left + 1) } return count }; 复制代码
5. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。 复制代码
和上题很相似，同样适用滑动窗口
var minSubArrayLen = function(target, nums) { let sum = 0 let min = nums.length + 1 let left = 0 for (let i = 0, len = nums.length; i < len; i++) { sum += nums[i] if (sum >= target) { while(sum - nums[left] >= target) { sum -= nums[left] left++ } min = Math.min(min, i - left + 1) } } return min === nums.length + 1 ? 0 : min }; 复制代码
总结
通过以上题型我们总结下知识点
- 滑动窗口实际是双指针的特殊题型
- 滑动窗口主要用于算法优化，可以简化多层循环为一层
- 小写字符的计数对比可以利用26位数组
- 滑动窗口主要适用于求字串的题型，可以是数组子串，字符子串
