JavaScript滑动窗口算法
1 思想
在力扣上刷题时经常可以看到这样的题，求XXX的子串、子数组、子序列等等，这类题一般使用滑动窗口来解决。本篇文章的思路学习了bilibili的up主红桃A士。
情况一：寻找最长的
初始化left，right，result，bestResult while (右指针没有到结尾) {
窗口扩大，加入right对应元素，更新当前result while (result不满足要求) {
窗口缩小，移除left对应元素，left右移 } 更新最优结果bestResult right++; } 返回bestResult 情况二：寻找最短的
初始化left，right，result，bestResult while (右指针没有到结尾) {
窗口扩大，加入right对应元素，更新当前result while (result不满足要求) {
更新最优结果bestResult 窗口缩小，移除left对应元素，left右移 } right++; } 返回bestResult 2 代码
下面以力扣的两道题来说明两种情况。
1、寻找最长的
var lengthOfLongestSubstring = function (s) {
let left = right = len = maxLen = 0; let arr = []; // 记录当前滑动窗口包含的字符 // 当右指针指向字符串最右边时停止循环 while (right < s.length) {
if (arr.includes(s[right])) {
// 如果滑动窗口中的字符串包含了右指针指向的元素 // 当arr中不包含右指针指向的字符，停止循环 while (arr.includes(s[right])) {
arr.shift(); // 删除最左边的元素 len--; // 更新当前的长度 left++; // 左指针右移 } // 循环结束后，arr中不包含右指针指向的元素 arr.push(s[right]); len++; right++; } else {
// 如果滑动窗口中的字符串不包含右指针指向的元素 arr.push(s[right]); len++; // 更新当前状态 if (len > maxLen) {
// 如果当前长度大于记录的最大长度，则更新最大长度 maxLen = len; } right++; } } return maxLen; }; 2、寻找最短的
var minSubArrayLen = function (target, nums) {
let left = 0, right = 0; // 定义左右指针 let result = 0; // 记录当前滑动窗口的值 let bestResult = 0; // 记录最优的值 while (right < nums.length) {
// 右指针移动到最右边《结束循环 result = result + nums[right]; // 记录当期滑动窗口的值 while (result >= target) {
// 如果当前的最好的结果大于左右指针之间的长度，更新最优结果 if (right - left + 1 < bestResult || bestResult == 0) {
bestResult = right - left + 1; } // 将左指针向右移，并且左指针的值从当前结果里面减掉 result -= nums[left]; left++; } right++; // 向右滑动窗口 } return bestResult; }; 版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/210712.html原文链接：https://javaforall.net
