建站公司最喜欢的网站网站整站优化

目录

一、滑动窗口的核心原理

二、滑动窗口的两种类型

1. 固定大小的窗口

2. 可变大小的窗口

三、实现细节与关键点

1. 窗口的初始化

2. 窗口的移动策略

3. 结果的更新时机

四、经典问题与代码示例

示例 1：和 ≥ target 的最短子数组（可变窗口）

示例 2：无重复字符的最长子串（哈希表辅助）

五、边界条件与易错点

1. 数组越界

2. 初始值的设置

3. 哈希表的使用

4. 循环条件错误

六、时间复杂度分析

七、滑动窗口的适用场景

八、滑动窗口的扩展

1. 结合前缀和

2. 结合单调队列

总结

---

一、滑动窗口的核心原理

        滑动窗口（Sliding Window） 是一种基于 双指针（Two Pointers） 的算法设计范式，核心思想是通过维护一个 动态窗口区间（[left, right]），在遍历过程中调整窗口的左右边界，避免重复计算，从而将时间复杂度优化到 O(n)。

• 核心逻辑：

  • 窗口扩张：right 指针向右移动，扩大窗口，直到满足某个条件。

  • 窗口收缩：一旦满足条件，left 指针向右移动，缩小窗口，直到不满足条件。

  • 更新结果：在窗口调整过程中，记录最优解。

---

二、滑动窗口的两种类型

1. 固定大小的窗口

• 特点：窗口长度固定为 k，通过滑动窗口的起始位置遍历所有可能的子区间。

• 典型问题：

  • 求长度为 k 的子数组的最大平均值

  • 长度为 k 的子字符串的排列匹配

C++ 代码模板：

int fixedWindow(vector<int>& nums, int k) 
{int sum = 0, max_sum = 0;// 初始化窗口for (int i = 0; i < k; ++i) sum += nums[i];max_sum = sum;// 滑动窗口for (int right = k; right < nums.size(); ++right) {sum += nums[right] - nums[right - k]; // 窗口右移，更新和max_sum = max(max_sum, sum);}return max_sum;
}

2. 可变大小的窗口

• 特点：窗口大小不固定，根据问题条件动态调整 left 和 right 指针。

• 典型问题：

  • 无重复字符的最长子字符串

  • 和大于等于 target 的最短子数组

C++ 代码模板：

int variableWindow(string s) 
{unordered_map<char, int> window;int left = 0, max_len = 0;for (int right = 0; right < s.size(); ++right) {char c = s[right];window[c]++; // 窗口扩张// 窗口收缩条件：出现重复字符while (window[c] > 1) {char d = s[left];window[d]--; // 移出左边界字符left++;}max_len = max(max_len, right - left + 1); // 更新结果}return max_len;
}

---

三、实现细节与关键点

1. 窗口的初始化

• 初始指针位置：通常 left = right = 0。

• 状态变量：如窗口内的和（sum）、哈希表（记录字符频率）等。

2. 窗口的移动策略

• 扩张条件：一般通过 for 循环逐步移动 right。

• 收缩条件：在满足特定条件时，通过 while 循环移动 left，直到条件不满足。

3. 结果的更新时机

• 固定窗口：每次窗口滑动后更新结果。

• 可变窗口：在窗口收缩后或扩张过程中更新结果。

---

四、经典问题与代码示例

示例 1：和 ≥ target 的最短子数组（可变窗口）

int minSubArrayLen(int target, vector<int>& nums) 
{int left = 0, sum = 0;int min_len = INT_MAX;for (int right = 0; right < nums.size(); ++right) {sum += nums[right]; // 窗口扩张while (sum >= target) { // 窗口收缩条件min_len = min(min_len, right - left + 1);sum -= nums[left++]; // 窗口收缩}}return min_len == INT_MAX ? 0 : min_len;
}

示例 2：无重复字符的最长子串（哈希表辅助）

int lengthOfLongestSubstring(string s) 
{unordered_map<char, int> last_pos; // 记录字符最后出现的位置int left = 0, max_len = 0;for (int right = 0; right < s.size(); ++right) {char c = s[right];// 若字符 c 已存在且在窗口内，移动 left 到 last_pos[c] + 1if (last_pos.count(c) && last_pos[c] >= left) {left = last_pos[c] + 1;}last_pos[c] = right; // 更新字符位置max_len = max(max_len, right - left + 1);}return max_len;
}

---

五、边界条件与易错点

1. 数组越界

• 在固定窗口中，需确保 right - k >= 0。

• 在可变窗口中，需检查 left 是否超过 right。

2. 初始值的设置

• 最小值初始化为 INT_MAX，最大值初始化为 INT_MIN。

3. 哈希表的使用

• 在字符频率统计中，需确保哈希表的键存在性（如用 count() 检查）。

4. 循环条件错误

• 错误：在收缩窗口时使用 if 而非 while，导致窗口未完全收缩。

• 正确：使用 while 循环确保窗口收缩到条件不满足。

---

六、时间复杂度分析

• 固定窗口：O(n)，每个元素被访问一次。

• 可变窗口：O(n)，每个元素最多被 left 和 right 各访问一次。

---

七、滑动窗口的适用场景

1. 连续子数组/子字符串问题

   • 最短/最长满足条件的子数组

   • 子数组的和/乘积/频率统计

2. 优化暴力解法

   • 将 O(n²) 的暴力枚举优化为 O(n)

3. 数据流处理

   • 实时处理数据流中的窗口统计量（如移动平均值）

---

八、滑动窗口的扩展

1. 结合前缀和

• 用于处理负数数组或更复杂的条件（如子数组和为 k）。

• 示例代码：

  int subarraySum(vector<int>& nums, int k) 
  {unordered_map<int, int> prefix_sum; // 前缀和 -> 出现次数prefix_sum[0] = 1;int sum = 0, count = 0;for (int num : nums) {sum += num;if (prefix_sum.count(sum - k)) {count += prefix_sum[sum - k];}prefix_sum[sum]++;}return count;
  }

2. 结合单调队列

• 用于维护窗口内的最大值/最小值（如滑动窗口最大值问题）。

• 示例代码：

  vector<int> maxSlidingWindow(vector<int>& nums, int k) 
  {deque<int> dq; // 存储下标，按值单调递减vector<int> res;for (int i = 0; i < nums.size(); ++i) {// 移除超出窗口的元素if (!dq.empty() && dq.front() == i - k) dq.pop_front();// 维护单调队列while (!dq.empty() && nums[i] >= nums[dq.back()]) dq.pop_back();dq.push_back(i);// 记录窗口最大值if (i >= k - 1) res.push_back(nums[dq.front()]);}return res;
  }

---

总结

滑动窗口的核心在于 双指针的协同移动 和 窗口状态的动态维护。掌握以下要点：

1. 明确窗口的 扩张与收缩条件。

2. 合理选择 数据结构（如哈希表、单调队列）维护窗口状态。

3. 注意 边界条件 和 初始值设置。

4. 灵活结合其他算法（如前缀和、单调队列）解决复杂问题。