湖南变电站公司中企动力技术支持网站建设,模板网站与定制开发网站的区别,阿里云学生免费服务器,江西网站开发哪家好文章目录 一、滑动窗口算法原理二、滑动窗口的常见应用场景三、滑动窗口的核心控制逻辑1. 判断条件的设计原则2. 窗口调整的触发时机3. 状态维护的关键技巧4. 常见错误与避坑指南 四、代码示例示例 1#xff1a;连续子数组的最大和#xff08;力扣题号#xff1a;53. 最大子… 文章目录 一、滑动窗口算法原理二、滑动窗口的常见应用场景三、滑动窗口的核心控制逻辑1. 判断条件的设计原则2. 窗口调整的触发时机3. 状态维护的关键技巧4. 常见错误与避坑指南 四、代码示例示例 1连续子数组的最大和力扣题号53. 最大子数组和示例 2无重复字符的最长子串力扣题号3. 无重复字符的最长子串 五、总结 在算法与数据结构的学习过程中滑动窗口是一个非常实用且高效的技巧尤其适用于处理数组、字符串等序列数据的问题。本文将深入探讨滑动窗口算法的原理、常见应用场景并通过 C 代码示例帮助大家更好地理解和掌握这一技巧。
一、滑动窗口算法原理
滑动窗口算法的核心思想是在一个给定大小的窗口内进行特定操作通过不断滑动窗口来更新窗口内的数据从而解决诸如查找符合条件的子数组、子字符串等问题。可以将滑动窗口想象成一个大小可变或固定的 “窗口”在数据序列上从左到右滑动每次滑动都会根据窗口内的数据进行相应的计算或判断。
一般来说滑动窗口算法包含两个关键指针左指针left和右指针right。这两个指针就像是窗口的左右边框它们界定了窗口的边界通过移动指针来扩大或缩小窗口的范围。为了让大家更直观地理解我们来模拟一个具体场景假设现在有一个整数数组[1, 3, 2, 5, 4]我们的目标是找到和不超过7的最长连续子数组。
初始状态 一开始左指针left和右指针right都指向数组的第一个元素此时窗口内只有一个元素1窗口内元素和为1满足和不超过7的条件 。扩大窗口 接下来右指针right向右移动一位纳入新元素3此时窗口内元素变为[1, 3]窗口内元素和更新为1 3 4依然满足条件。继续扩大窗口右指针再右移一位纳入元素2窗口内元素变为[1, 3, 2]元素和为1 3 2 6还是满足条件。缩小窗口 当右指针继续右移纳入元素5后窗口内元素变为[1, 3, 2, 5]元素和为1 3 2 5 11超过了7此时就需要缩小窗口。左指针向右移动一位将元素1移出窗口窗口内元素变为[3, 2, 5]元素和更新为3 2 5 10还是超过7左指针继续右移将元素3移出窗口此时窗口内元素变为[2, 5]元素和为2 5 7重新满足条件。判断条件 在每次窗口变化后我们都要根据具体问题的要求判断窗口内的数据是否满足条件。在这个例子中我们每一次调整完窗口都要记录当前窗口的长度与之前记录的最长长度进行比较保留更长的那个。通过这样不断地扩大和缩小窗口最终就能找到和不超过7的最长连续子数组。 其基本操作如下
扩大窗口右指针右移将新元素纳入窗口内更新窗口内的状态如计算窗口内元素的和、统计不同元素的个数等。缩小窗口左指针右移将元素移出窗口同样需要更新窗口内的状态。判断条件在每次窗口变化后根据具体问题的要求判断窗口内的数据是否满足条件若满足则记录结果或进行相应操作。
二、滑动窗口的常见应用场景
查找最长 / 最短子数组 / 子字符串 例如给定一个整数数组和一个目标值要求找出数组中和为目标值的最长子数组或者在字符串中找出包含所有给定字符的最短子字符串。这类问题可以通过滑动窗口不断调整窗口大小记录满足条件的最长或最短窗口。求固定大小窗口内的最大值 / 最小值 在一些场景中需要在一个长度固定的滑动窗口内找到最大值或最小值。例如在股票交易中计算连续几天内的最高股价。此时可以使用滑动窗口配合数据结构如单调队列高效解决。统计满足特定条件的子数组 / 子字符串数量 比如统计字符串中不含有重复字符的子字符串数量或者在数组中找出和小于某个值的子数组数量等。通过滑动窗口动态维护窗口内的数据状态进而统计符合条件的数量。
三、滑动窗口的核心控制逻辑
滑动窗口算法的高效性源于其精准的时机控制 —— 何时扩大窗口、何时缩小窗口、何时记录结果。本节将通过实例和代码揭示滑动窗口的控制秘诀。
1. 判断条件的设计原则
判断条件决定了窗口的行为模式。设计时需遵循以下原则
完整性原则覆盖所有可能的边界情况
// 错误示例未处理空数组
if (nums.empty()) return 0; // 正确做法添加边界检查// 错误示例未处理找不到解的情况
return s.substr(startIndex, minLen); // 正确做法检查minLen是否更新单调性原则窗口状态变化应具有单调性
扩大窗口右指针右移状态单调递增如和增大、字符数增加缩小窗口左指针右移状态单调递减
即时性原则每次窗口调整后立即进行判断
while (right n) {// 扩大窗口currentSum nums[right];right;// 立即判断是否需要缩小窗口while (currentSum target) {currentSum - nums[left];left;}// 更新结果每次窗口稳定后立即判断if (right - left maxLen) {maxLen right - left;}
}2. 窗口调整的触发时机
窗口调整时机直接影响算法效率常见触发模式有
条件驱动型当窗口状态满足 / 不满足某条件时调整
示例寻找和≥target 的最短子数组
while (right n) {sum nums[right];right;// 当窗口和≥target时尝试缩小窗口while (sum target) {minLen min(minLen, right - left);sum - nums[left];left;}
}固定大小型窗口大小固定滑动时保持大小不变
示例计算每个大小为 k 的子数组的平均值
for (right 0; right n; right) {sum nums[right];// 当窗口达到k大小时开始计算并滑动if (right k - 1) {avg sum / k;sum - nums[right - k 1]; // 移除窗口最左侧元素}
}双条件驱动型结合两个条件共同控制窗口
示例寻找包含所有目标字符的最短子串
while (right n) {// 扩大窗口直到包含所有目标字符addCharToWindow(s[right]);right;// 当窗口包含所有目标字符时尝试缩小窗口while (windowContainsAllChars()) {updateMinLen();removeCharFromWindow(s[left]);left;}
}3. 状态维护的关键技巧
窗口状态维护是滑动窗口的核心难点常见技巧包括
计数器数组适用于字符统计
int targetCount[256] {0}; // 统计目标字符出现次数
int windowCount[256] {0}; // 统计窗口内字符出现次数// 初始化目标字符计数
for (char c : t) targetCount[c];// 窗口滑动时更新计数
windowCount[s[right]];
windowCount[s[left]]--;哈希表适用于动态维护字符频率
unordered_mapchar, int targetMap;
unordered_mapchar, int windowMap;// 检查窗口是否包含所有目标字符
bool isValid() {for (auto p : targetMap) {if (windowMap[p.first] p.second) return false;}return true;
}单调队列高效维护窗口最大值 / 最小值
dequeint q; // 存储元素下标// 窗口滑动时维护队列单调性
while (!q.empty() nums[q.back()] nums[right]) {q.pop_back();
}
q.push_back(right);// 移除超出窗口范围的元素
if (q.front() right - k) {q.pop_front();
}// 当前窗口最大值为nums[q.front()]4. 常见错误与避坑指南
在实现滑动窗口时常见的错误包括
指针移动顺序错误 错误先缩小窗口再扩大窗口正确先扩大窗口再根据条件缩小窗口 状态更新不及时 错误在窗口调整后未更新统计信息正确每次指针移动后立即更新状态 边界条件处理不当 错误忽略空数组、单元素数组等情况正确在算法开始前处理边界条件 结果更新时机错误 错误仅在缩小窗口后更新结果正确在窗口状态稳定时扩大或缩小后都进行结果更新
四、代码示例
示例 1连续子数组的最大和力扣题号53. 最大子数组和
#include iostream
#include vector
using namespace std;int maxSubArraySum(vectorint nums) {int n nums.size();if (n 0) return 0;int currentSum nums[0];int maxSum nums[0];for (int i 1; i n; i) {// 如果当前和为负数丢弃之前的子数组从当前元素重新开始currentSum max(nums[i], currentSum nums[i]);// 更新最大和maxSum max(maxSum, currentSum);}return maxSum;
}在这段代码中我们使用滑动窗口的思想来寻找具有最大和的连续子数组。通过遍历数组维护一个当前和 currentSum如果当前和为负数则丢弃之前的子数组从当前元素重新开始计算和。同时不断更新最大和maxSum。
示例 2无重复字符的最长子串力扣题号3. 无重复字符的最长子串
#include iostream
#include string
#include vector
using namespace std;int lengthOfLongestSubstring(string s) {int n s.length();if (n 0) return 0;// 用于记录字符最后一次出现的位置vectorint charIndex(128, -1);int left 0;int maxLen 0;for (int right 0; right n; right) {char c s[right];// 如果字符c在窗口内出现过调整左指针if (charIndex[c] left) {left charIndex[c] 1;}// 更新字符c的最后出现位置charIndex[c] right;// 计算当前窗口的长度maxLen max(maxLen, right - left 1);}return maxLen;
}这个示例展示了如何使用滑动窗口找到字符串中不含有重复字符的最长子串。我们使用一个数组charIndex来记录每个字符最后一次出现的位置。右指针right不断向右移动当遇到重复字符时调整左指针left的位置确保窗口内没有重复字符。
五、总结
滑动窗口算法通过灵活调整窗口大小能够高效地解决许多与序列数据相关的问题。在实际应用中关键在于根据具体问题确定窗口的扩大和缩小条件以及如何正确维护窗口内的数据状态。通过不断练习和实践相信大家能够熟练掌握这一强大的算法技巧在算法竞赛和实际开发中灵活运用。
