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

空白诗

发布于 2024-07-20 12:46:41

620

发布于 2024-07-20 12:46:41

文章被收录于专栏：【全栈开发之路】

滑动窗口（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)：如果子数组和大于等于目标值，更新最小长度，并缩小窗口范围。