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

🔥 个人主页：空白诗

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

---

一、算法原理

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

1. 初始化窗口的起始位置和结束位置。
2. 移动窗口的结束位置，扩展窗口的范围。
3. 在窗口范围内进行计算，检查是否满足问题的条件。
4. 如果条件不满足，移动窗口的起始位置，缩小窗口的范围。
5. 重复步骤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

注释说明：

1. 最长无重复字符子串：

   • set：用于存储窗口内的字符，避免重复。
   • left 和 right：分别表示窗口的起始位置和结束位置。
   • maxLength：用于记录最长无重复字符子串的长度。
   • while (right < s.length)：遍历字符串。
   • if (!set.has(s[right]))：如果字符不在集合中，加入集合并更新窗口大小和最长长度。
   • else：如果字符在集合中，删除起始位置的字符并移动起始位置。

2. 长度最小的子数组：

   • left 和 right：分别表示窗口的起始位置和结束位置。
   • sum：用于记录窗口内的子数组和。
   • minLength：用于记录满足条件的最小子数组长度。
   • while (right < nums.length)：遍历数组。
   • while (sum >= target)：如果子数组和大于等于目标值，更新最小长度，并缩小窗口范围。

---

三、应用场景

1. 字符串处理：如查找最长无重复字符子串、包含所有字符的最小子串等。
2. 数组处理：如查找和大于等于目标值的最小子数组、固定大小的最大或最小子数组和等。
3. 数据流处理：滑动窗口算法可以用于实时处理数据流，计算动态窗口内的数据特征。

---

四、总结

滑动窗口算法是一种高效解决数组或字符串中子数组（子串）问题的算法技巧，通过动态调整窗口的大小和位置，可以在O(n)时间复杂度内解决许多实际问题。理解和掌握滑动窗口算法，可以有效解决字符串处理、数组处理和数据流处理等问题。

---

原文地址：https://blog.csdn.net/m0_52827996/article/details/140558025

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！