javascript怎么实现数组滑动窗口

滑动窗口可通过双指针维护一个动态子数组来高效解决连续子序列问题，其核心是通过扩展和收缩窗口寻找满足条件的最短或最长子数组；具体步骤为：①初始化start和end指针为0；②扩展end指针并累加元素直至满足条件；③收缩start指针并更新结果，直到不再满足条件；④记录过程中最优解；例如求和为target的最短子数组时，时间复杂度为o(n)，每个元素最多被访问两次；当数组含负数时，因和可能回升，需更谨慎判断收缩时机；滑动窗口是双指针的特例，专用于连续区间问题，典型应用包括求和为目标值的子数组、最长无重复字符子串等。

JavaScript实现数组滑动窗口，本质上就是通过控制两个指针，在一个数组上形成一个可变大小的“窗口”，然后在这个窗口内进行计算或操作。关键在于如何移动这两个指针，以及在移动的过程中做什么。

滑动窗口的核心在于维护一个动态的子数组（窗口），通过移动窗口的起始和结束位置，实现对数组不同子集的处理。

如何理解滑动窗口？

滑动窗口其实是一种抽象的概念，它代表了对数组（或者字符串）一段连续区间的观察。想象一下，你拿着一个放大镜（窗口）在一个很长的卷轴（数组）上移动，每次只能看到放大镜覆盖的部分。

滑动窗口的基本步骤

1. 初始化窗口：定义窗口的起始位置

   start

   和结束位置

   end

   ，通常初始时

   start = 0

   ，

   end = 0

   。
2. 扩展窗口：不断增加

   end

   ，直到窗口满足特定条件。
3. 收缩窗口：当窗口满足条件后，尝试增加

   start

   ，减小窗口大小，直到不再满足条件。
4. 记录结果：在窗口移动的过程中，记录下满足条件的结果。

滑动窗口的典型应用场景

滑动窗口擅长解决数组或字符串中，需要找出满足特定条件的连续子数组（或子字符串）的问题。比如：

• 找到数组中和为特定值的连续子数组。
• 找到字符串中最长的无重复字符的子串。
• 计算数组中每个固定大小窗口内的最大值/最小值。

JavaScript代码示例：求数组中和为target的最短连续子数组

function minSubArrayLen(nums, target) {
  let start = 0;
  let end = 0;
  let sum = 0;
  let minLen = Infinity; // 初始化为无穷大，方便比较

  while (end = target) {
      minLen = Math.min(minLen, end - start + 1); // 更新最小长度
      sum -= nums[start];
      start++;
    }

    end++;
  }

  return minLen === Infinity ? 0 : minLen; // 如果没有找到，返回0
}

// 示例
const nums = [2, 3, 1, 2, 4, 3];
const target = 7;
console.log(minSubArrayLen(nums, target)); // 输出 2 (因为 [4, 3] 是和为7的最短子数组)

这段代码展示了滑动窗口的精髓：先扩展窗口，直到窗口内的和大于等于目标值，然后收缩窗口，尝试找到更短的满足条件的子数组。

minLen

变量记录了找到的最小长度，如果循环结束时

minLen

仍然是

Infinity

，说明没有找到符合条件的子数组。

如何处理负数数组？

如果数组中包含负数，求和问题会变得稍微复杂一些。因为负数的加入，可能导致窗口的和在收缩时反而增大。此时，不能简单地通过

sum >= target

来判断是否需要收缩窗口。

解决方法之一是，记录下每次窗口内的和，并与之前的最小值进行比较。当窗口的和小于最小值时，更新最小值。同时，需要更谨慎地控制窗口的收缩，避免错误地丢弃有用的负数。

滑动窗口和双指针有什么区别？

滑动窗口可以看作是双指针的一种特殊形式。双指针更通用，可以用于解决各种数组和链表问题，而滑动窗口则专注于解决连续子数组（或子字符串）的问题。滑动窗口的两个指针通常具有明确的含义：窗口的起始和结束位置。

滑动窗口的时间复杂度

滑动窗口的时间复杂度通常是 O(n)，其中 n 是数组的长度。这是因为每个元素最多被访问两次：一次在扩展窗口时，一次在收缩窗口时。虽然看起来像是嵌套循环，但实际上每个元素只会被处理有限的次数，因此总体时间复杂度是线性的。

Java免费学习笔记：立即学习
解锁 Java 大师之旅：从入门到精通的终极指南