经常会有人问,作为前端,你在实际工作中用到过哪些算法,之前我回答是,树和位运算,而最近在学习网络模块,发现了和前端,起码是和网络相关的一种算法,那就是 滑动窗口
;
我们知道在 HTTP1.1 发送请求,TCP 会将请求传输到服务端,而对于 TCP 协议,最重要的能力之一就是控制流速;
当发送方需要发送很多请求的时候,这些请求会阻塞在某一个缓存中等待 TCP 发送,这个后面还有源源不断的请求发起,那总不能一下子全堵在缓存上吧,会炸掉的,这个时候这个模型就是滑动窗口了
发送过程有三个状态:
这个时候 TCP 能够缓存的请求数就是一个窗口,每当浅绿色转成深绿色,那么窗口就可以像右边滑动,而窗口还保留的状态依然可以复用,这就是滑动窗口
的魅力了
滑动窗口最大特点是,滑动窗口过程中,保留在窗口里的数据状态直接复用,不需要再次构建,节约资源;
那么接下来我们通过做题来熟悉一下滑窗,并看看是否有更多不一样的情况吧;
根据滑窗窗口大小是否固定,分成了两种:固定大小的窗口
和 可变窗口大小
;
前言谈及的 TCP 中的滑窗情况,其实是一个固定大小的滑窗,当然也可以先给定部分大小,然后根据流速进行扩展,那是后续的操作了;
而更多的情况是不固定大小的滑窗,这类滑窗一般都是创建过程中,一股脑子将资源耗尽去扩大窗口,达到一个阈值,然后再收缩窗口,根据具体题目,达到一个平衡了;
这其实就好像是一个快速试错过程,先将情况推到极致了,然后加入对应的变量来收缩窗口,找到比较合适的一个情况,等到合规的情况在窗口里打破了,就重新扩展;
滑窗其实在理解题意的时候,又有点一分为二的感觉,就是我可以将窗口里的状态和窗口外的状态切分开,但是他们又是此消彼长
的关系,这样不断权衡,达到一个动态平衡的状态,就是某些题的结果
固定大小的窗口
可变窗口大小
参考视频:传送门
某种情况的子数组有多少个
,这样就得将所有情况都弄出来,但是如果只是要求一个极值,比方说这些符合要求的情况中,最小是多少,那么就没必要用双滑窗了,因为 r 指针的移动肯定会扩大窗口,所以 l 指针只需要保留对应的极值(第一个或者最后一个),然后求出极值即可滑窗是双指针的一种特殊情况,我们在使用双指针处理问题的时候,可能不会考虑前一个窗口里的状态值,只是将所有情况都考虑进行,这样就会有很多计算是重复的,滑窗就是一种优化了的双指针情况。
所以算法还是有点用的,起码在初级的时候,我们可以更好的理解我们使用的工具的内核,而不仅仅只是雾里看花,知其然不知其所以然;
所以加油!!
@分析
var findAnagrams = function (s, p) {
const pMap = new Map();
const sMap = new Map();
let ret = []; // 存储合乎要求的首个字符
for (let pp of p) {
pMap.set(pp, pMap.get(pp) ? pMap.get(pp) + 1 : 1);
}
let valid = 0; // 存储合乎 p 的变量
let l = (r = 0);
while (r < s.length) {
const rr = s[r];
sMap.set(rr, sMap.get(rr) ? sMap.get(rr) + 1 : 1);
if (sMap.get(rr) === pMap.get(rr)) {
// 两个 key 对应的 value 值一致的时候,才会增加 valid
valid++;
}
// 如果加上这个 r 这个字符,长度超出了固定窗口的长度,则需要先收缩 l, 再判定
if (r - l === p.length) {
// 从进入到这里逻辑开始,其实就是属于固定窗口两侧的指针一起跑,这里是 l 指针开始跑,之前因为还没初始化完窗口
const ll = s[l];
if (pMap.get(ll) === sMap.get(ll)) {
// 如果收缩过程中的这个值属于 valid 的
valid--;
}
sMap.set(ll, sMap.get(ll) - 1);
l++;
}
if (valid === pMap.size) {
// 合乎要求
ret.push(l);
}
r++;
}
return ret;
};
// 3. 无重复字符的最长子串
分析
1. 这里求的是最长的子串,证明有很多长度不一的子串,那么就是有很多大小不一的窗口,所以属于窗口不固定的滑窗题
2. 初始化 l r ,初始化一个 map 用来存放窗口里的字符的
3. map 是用来做条件判断的,判断窗口扩展过程中是否和已有的窗口字符重复了,如果重复了,那么就要收缩窗口 s[r]=== s[l] 然后 l++,
4. 然后不管是否整理窗口, r 指针都会继续扩展下去,所以处理完了,需要重新加上 s[r], 并继续走下去
5. 时间复杂度 ${O(n)}$ 因为 r 指针遍历一次,走的过程中遇到重复值 ,l 指针移动,最多 l 也就遍历一次,也就是最多直走了 2n
6. 空间复杂度 $(O(k))$ k 是最大的窗口size
var lengthOfLongestSubstring = function(s) {
const map = new Map() // 这个用来存放
let l = r = 0
let max = 0
while(r<s.length) {
if(map.has(s[r])){
// 说明窗口里的值已经出现重复了,所以需要整理窗口
max = Math.max(max,map.size) // 存一下大小
// 开始收缩窗口,找出 s[r] 同值的那个位置
while(s[l] !== s[r]){
map.delete(s[l])
l++
}
// 找到了 -- 再移除一下
map.delete(s[l])
l++
}
// 将当前 s[r] 字符存起来
map.set(s[r],1)
r++
}
// 这个时候 r 走到底了,
return Math.max(max,map.size)
}
console.log(lengthOfLongestSubstring("aab"))
分析
var lengthOfLongestSubstring = function(s) {
const map = new Map() // 这个用来存放窗口出现过的值
let l = r = 0
let max = 0
while(r<s.length) {
if(map.has(s[r]) && map.get(s[r])>=l){
// 已经遍历过了这个值且在当前的这个窗口里
max = Math.max(max,r-l) // 先存一下大小
l = map.get(s[r]) +1 // 跳到重复出现字符前面去了
}
// 将当前 s[r] 字符存起来,并将字符的下标也存起来 -- or 更新一下罪行 s[r] 的位置
map.set(s[r],r)
r++
}
// 这个时候 r 走到底了,
return Math.max(max,r-l)
}
分析
function minWindow(s, t) {
const sMap = new Map();
const tMap = new Map();
// 先将 t 存起来
for (let tt of t) {
tMap.set(tt, tMap.get(tt) ? tMap.get(tt) + 1 : 1);
}
let ret = "";
let l = (r = 0); // 不固定的滑窗的初始化
let valid = 0; //表示窗口中匹配 t 字符的数量 -- 匹配的字符是指:字符 ss 在窗口里的数量超过了 ss 在 t 字符串中这个字符数量
while (r < s.length) {
const ss = s[r];
sMap.set(ss, sMap.get(ss) ? sMap.get(ss) + 1 : 1); //存起来
if (sMap.get(ss) === tMap.get(ss)) {
// 证明 ss 已经匹配了
valid++;
}
if (valid === tMap.size) {
// 窗口里的字符串已经完全匹配了,那么就需要收缩一下了
while (sMap.get(s[l]) !== tMap.get(s[l])) {
// 因为现在的初始条件是: 对于某个字符 s[l], sMap.get(s[l])>=tMap.get(s[l])
// 所以可以干掉一些,知道 === 的时候
sMap.set(s[l], sMap.get(s[l]) - 1);
l++;
}
if (r - l + 1 < ret.length || !ret.length) {
// 如果长度更小了,或者初始化的 ret, 那就替换一下吧
ret = s.slice(l, r + 1);
}
// 继续走吧,总得砍掉一个 valid 的,
sMap.set(s[l], sMap.get(s[l]) - 1);
valid--; // 少了一个 s[l] 了
l++;
}
r++;
}
return ret;
}
分析
var minSubArrayLen = function (target, nums) {
let ret = Infinity;
let l = (r = 0);
let sum = 0;
while (r < nums.length) {
sum += nums[r];
while (sum >= target) {
// 符合要求,开始压缩窗口大小
ret = Math.min(ret, r - l + 1); // 更新一下
sum -= nums[l];
l++;
}
r++
}
return ret === Infinity ? 0: ret
};
分析
var totalFruit = function(fruits) {
const map = new Map() // 篮子,大小为2,用来存储当前窗口下的水果
let ret = 0
let l = r =0
while(r < fruits.length){
ret = Math.max(ret,r-l); // 先保存一下上一次的大小
const rr = fruits[r]
map.set(rr,map.get(rr)?map.get(rr)+1:1)
// 如果超了,则需要收缩一整类的树
while(map.size > 2){
// 长度超了,向左收缩
const ll = fruits[l]
if(map.get(ll) === 1){
map.delete(ll)
}else{
map.set(ll,map.get(ll)-1)
}
l++
}
r++
}
return Math.max(ret,r-l);
};
分析 -- 双滑动窗口
var numSubarraysWithSum = function (nums, goal) {
let ret = 0
let l1 = 0, l2 = 0
let sum1 = 0,sum2 = 0 // sum1 <= goal, sum2 < goal
let r = 0
while(r<nums.length){
sum1+=nums[r]
while(l1<=r && sum1>goal){
sum1-=nums[l1]
l1++
}
sum2+=nums[r]
while(l2<=r && sum2>=goal){
sum2-=nums[l2]
l2++
}
ret+= l2-l1
r++
}
return ret
}
分析 -- 双指针
var numSubarraysWithSum = function (nums, goal) {
let ret = 0;
for (let i = 0; i < nums.length; i++) {
// 固定i指针
let sum = 0;
let r = i;
while (r <= nums.length) {
sum += nums[r];
if (sum === goal) ret++;
r++;
}
}
return ret;
};
分析 -- 前缀和
var numSubarraysWithSum = function (nums, goal) {
const map = new Map()
let prevSum = 0
let ret = 0
for(let num of nums){
prevSum+=num
if(map.has(prevSum-goal)){
ret+=map.get(prevSum-goal)
}
if(prevSum === goal){
ret++
}
map.set(prevSum,map.get(prevSum)?map.get(prevSum)+1:1)
}
return ret
};
分析
var subarraysWithKDistinct = function (nums, k) {
let ret = 0;
const map1 = new Map(); // 用来存储窗口中值和出现的次数
const map2 = new Map(); // 用来存储窗口中值和出现的次数
let l1 = (l2 = 0);
let r = 0
while (r < nums.length) {
const rr = nums[r];
map1.set(rr, map1.get(rr) ? map1.get(rr) + 1 : 1);
map2.set(rr, map2.get(rr) ? map2.get(rr) + 1 : 1);
while (map1.size > k) {
// 窗口的变量已经超过了 k,所以需要 l 指针收缩
const ll = nums[l1];
l1++;
if (map1.get(ll) === 1) {
map1.delete(ll);
} else {
map1.set(ll, map1.get(ll) - 1);
}
}
while (map2.size >= k) {
// 窗口的变量已经超过了 k,所以需要 l 指针收缩
const ll = nums[l2];
l2++;
if (map2.get(ll) === 1) {
map2.delete(ll);
} else {
map2.set(ll, map2.get(ll) - 1);
}
}
ret += l2-l1
r++;
}
return ret;
};
分析
var maxTurbulenceSize = function (arr) {
const len = arr.length;
let max = 1; // 最少是 1
let l = 0,
r = 0; // 来个初始值
while (r < len - 1) {
if (l === r) {
// 上一次比对不符合要求
if (arr[l] === arr[l + 1]) {
// 去重
l++;
}
r++;
} else {
// 有和下一个进行比对
if (arr[r - 1] < arr[r] && arr[r] > arr[r + 1]) {
r++;
} else if (arr[r - 1] > arr[r] && arr[r] < arr[r + 1]) {
r++;
} else {
// 不符合要求
l = r;
}
}
max = Math.max(max, r - l + 1);
}
return max;
};
分析
var longestOnes = function (nums, k) {
const changeArr = []; // 用 arr 来存储从 0-1 的下标的值
let l = (r = 0);
let ret = 0;
while (r < nums.length) {
const rr = nums[r];
if (k === 0) {
// 特殊情况,不做任何处理
if (rr === 0) {
ret = Math.max(ret, r - l); // 先保存当前的这个长度
l = r + 1;
}
} else {
if (rr === 0 && changeArr.length === k) {
// 当前值是 0,且已经变更了 k 次,无法再变了
ret = Math.max(ret, r - l); // 先保存当前的这个长度
// 由于是连续的变动,所以 l 可以直接指向第一个变动值之前
l = changeArr.shift() + 1;
}
if (rr === 0 && changeArr.length < k) {
changeArr.push(r);
}
}
r++;
}
return Math.max(ret, r - l);
};
console.log(longestOnes([0, 0, 1, 1, 1, 0, 0], 0));
分析
var balancedString = function (s) {
const n = s.length;
const max = n / 4; // 这里 n 就是 4 的倍数,入参会做好设定的
const map = new Map();
map.set("Q", 0);
map.set("W", 0);
map.set("E", 0);
map.set("R", 0);
for (let ss of s) {
map.set(ss, map.get(ss) + 1 );
}
let valid = 0; // 有多少个变量满足小于等于 n/4
[...map.values()].forEach((v) => {
if (v <= max) valid++;
});
if (valid === 4) return 0; //特殊情况,直接结束
let l = (r = 0);
let ret = Infinity;
while (r < n) {
const rr = s[r];
map.set(rr, map.get(rr) - 1);
if (map.get(rr) === max) {
// 如果减去之后刚好符合要求,则 valid 增加
valid++;
}
while (valid === 4) {
// 窗口符合要求,开始收缩窗口
ret = Math.min(ret, r - l + 1); // 先缓存一个
const ll = s[l];
l++;
map.set(ll, map.get(ll) + 1); //收缩滑窗,则滑出去的加入到 map 中去
if (map.get(ll) > max) valid--;
}
// 一直使得 valid 的值少于 4为止
r++;
}
return ret;
}
@分析
var numberOfSubarrays = function(nums, k) {
let ret = 0
let odd1 = 0
let odd2 = 0
let l1 = l2 = r = 0
while(r<nums.length){
const rr = nums[r]
if(rr%2){
odd1++
odd2++
}
while(odd1>k){
// 收缩 l1
const ll =nums[l1]
l1++
if(ll%2) odd1--
}
while(odd2 >= k){
// 收缩 l1
const ll =nums[l2]
l2++
if(ll%2) odd2--
}
// 这个时候 [l1,l2) 都属于可以合格的数组
ret+=l2-l1
r++
}
return ret
};
分析
var minOperations = function(nums, x) {
const len = nums.length
const total = nums.reduce((prev,cur) => prev+cur,0)
if(total<x) return -1 //边界,如果总和都不达 x, 那就直接跑路吧
let ret = Infinity //最少的操作数
let sum = 0
let l =r =0
while(r<len){
sum+=nums[r]
while(total-sum<x){
// 外面的值已经小于 x 了,所以需要收缩窗口
sum-=nums[l]
l++
}
if(total-sum === x){
// 符合要求
ret= Math.min(ret,len-(r-l+1))
}
r++
}
return ret=== Infinity?-1:ret
};
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。