当前位置：首页 > news >正文

【JavaScript 算法】滑动窗口：处理子数组问题

news 来源：原创 2024/9/20 15:36:50

在这里插入图片描述

🔥 个人主页：空白诗

在这里插入图片描述

文章目录

- 一、算法原理
- 二、算法实现
- - 示例问题1：最长无重复字符子串
  - 示例问题2：长度最小的子数组
  - 注释说明：
- 三、应用场景
- 四、总结

在这里插入图片描述

滑动窗口（Sliding Window）是一种高效解决数组或字符串中子数组（子串）问题的算法技巧。它通过在数组上维护一个窗口（区间），动态地调整窗口的大小和位置，从而高效地解决问题。本文将详细介绍滑动窗口算法的原理、实现及其应用。

一、算法原理

滑动窗口算法通过在数组上维护一个窗口来解决子数组问题。窗口的大小和位置可以动态调整，以满足不同问题的需求。滑动窗口的基本思想是：

初始化窗口的起始位置和结束位置。
移动窗口的结束位置，扩展窗口的范围。
在窗口范围内进行计算，检查是否满足问题的条件。
如果条件不满足，移动窗口的起始位置，缩小窗口的范围。
重复步骤2-4，直到遍历完整个数组。

在这里插入图片描述

二、算法实现

示例问题1：最长无重复字符子串

给定一个字符串，找出其中不含有重复字符的最长子串的长度。

/*** 找出字符串中最长无重复字符子串的长度* @param {string} s - 输入字符串* @return {number} - 最长无重复字符子串的长度*/
function lengthOfLongestSubstring(s) {const set = new Set();let left = 0;let right = 0;let maxLength = 0;while (right < s.length) {if (!set.has(s[right])) {set.add(s[right]);right++;maxLength = Math.max(maxLength, right - left);} else {set.delete(s[left]);left++;}}return maxLength;
}// 示例
const s = "abcabcbb";
console.log(lengthOfLongestSubstring(s)); // 输出: 3

示例问题2：长度最小的子数组

给定一个含有正整数的数组和一个正整数 target，找出该数组中满足其和大于等于 target 的长度最小的子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

/*** 找出和大于等于 target 的长度最小的子数组的长度* @param {number} target - 目标和* @param {number[]} nums - 输入数组* @return {number} - 长度最小的子数组的长度*/
function minSubArrayLen(target, nums) {let left = 0;let right = 0;let sum = 0;let minLength = Infinity;while (right < nums.length) {sum += nums[right];right++;while (sum >= target) {minLength = Math.min(minLength, right - left);sum -= nums[left];left++;}}return minLength === Infinity ? 0 : minLength;
}// 示例
const target = 7;
const nums = [2, 3, 1, 2, 4, 3];
console.log(minSubArrayLen(target, nums)); // 输出: 2

注释说明：

最长无重复字符子串：
- set：用于存储窗口内的字符，避免重复。
- left 和 right：分别表示窗口的起始位置和结束位置。
- maxLength：用于记录最长无重复字符子串的长度。
- while (right < s.length)：遍历字符串。
- if (!set.has(s[right]))：如果字符不在集合中，加入集合并更新窗口大小和最长长度。
- else：如果字符在集合中，删除起始位置的字符并移动起始位置。
长度最小的子数组：
- left 和 right：分别表示窗口的起始位置和结束位置。
- sum：用于记录窗口内的子数组和。
- minLength：用于记录满足条件的最小子数组长度。
- while (right < nums.length)：遍历数组。
- while (sum >= target)：如果子数组和大于等于目标值，更新最小长度，并缩小窗口范围。