Leetcode滑动窗口的使用

1.滑动窗口

1.1 什么是滑动窗口？

滑动窗口是一种处理数组或序列数据时常用的数据结构和算法思想。在计算机科学中，它通常涉及在数组上设置一个可变的窗口，该窗口可以向右（或向左）“滑动”，以覆盖不同的元素组合。这个窗口定义了一个固定的大小，或者根据特定条件动态调整大小，从而帮助我们解决一系列问题，如查找子数组、统计字符频率、计算最大/最小值、求和等等。

滑动窗口算法的关键步骤包括：

1. 初始化窗口：在序列的起始位置设定一个大小为 k 的窗口。
2. 窗口滑动：逐步向右（或按需向左）移动窗口，每次移动通常涉及移除最左边的元素并添加最右边的新元素到窗口中，保持窗口大小不变。
3. 检查条件：在每次窗口滑动后，检查当前窗口内的元素是否满足某个预设条件（如总和达到目标值、所有元素唯一等）。
4. 记录结果：如果满足条件，记录或更新所需的结果（如窗口大小、窗口内元素等）。

滑动窗口技术广泛应用于各种问题解决中，比如在字符串中查找无重复字符的最长子串、计算固定大小内的最大值或最小值、连续子数组问题等。它通过减少遍历和重计算的次数，提高了算法效率。

1.2 解题思路

题目原文：

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的

子数组

[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

解题思路：

详细步骤：

1. 初始化:
   • result 初始化为 INT32_MAX，用于存储满足条件的最短子数组长度。由于我们要找的是最小长度，初始设定一个极大值确保后续可以被任何有效的子数组长度替换。
   • i 和 j 分别作为滑动窗口的左右边界，初始时窗口内不包含任何元素，因此 i = j = 0。
   • sum 初始化为 0，用于累计窗口内元素的和。
2. 扩展窗口:
   • 通过移动右边界 j 向前（j++），并将新元素加入窗口（累加到 sum），不断尝试扩展窗口，直到窗口内元素之和 sum 至少等于 target。
3. 收缩窗口与更新结果:
   • 当窗口内元素和 sum 大于等于 target 时，说明找到了一个满足条件的子数组。此时，计算子数组长度 SubLength = j - i + 1。
   • 检查当前子数组长度是否小于之前记录的最小长度 result，如果是，则更新 result 为当前子数组长度。
   • 为了寻找更短的子数组，从窗口中移除最左侧的元素（减去 nums[i++]），同时收缩窗口，继续寻找其他可能的子数组。
4. 遍历数组:
   • 上述扩展与收缩窗口的过程在数组 nums 的每个元素上迭代执行，直到右边界 j 遍历完整个数组。
5. 处理结果:
   • 最后，检查 result 是否仍为初始值 INT32_MAX，如果是，则说明未找到满足条件的子数组，返回 0；否则，返回 result 作为最短子数组的长度。

题解：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int result = INT32_MAX;int i = 0;int sum = 0;int SubLength = 0;for(int j = 0;j < nums.size();++j){sum += nums[j];while(sum >= target){SubLength = j - i + 1;result = result < SubLength ? result : SubLength;sum -= nums[i++];}}return result == INT32_MAX ? 0 : result;}
};

1. int result = INT32_MAX;: 初始化结果变量 result 为 INT32_MAX，这是一个表示32位有符号整数最大值的常量。这样做是因为我们要寻找的是最小长度，初始化为一个极大值可以保证后续任何找到的有效长度都能替换这个初始值。

2. int i = 0;: 初始化左指针 i 为0，用于标记滑动窗口的开始位置。

3. int sum = 0;: 初始化当前窗口内元素的和 sum 为0。

4. int SubLength = 0;: 初始化一个临时变量 SubLength 用于存储当前窗口的长度。

5. for(int j = 0;j < nums.size();++j){: 使用一个外层循环，由指针 j 控制遍历数组 nums 的每一个元素。

6. sum += nums[j];: 在每次迭代中，将当前元素 nums[j] 加入到 sum 中，即扩展滑动窗口的和。

7. while(sum >= target){: 如果当前窗口的和 sum 大于等于目标值 target，则进入内部循环尝试缩小窗口并更新结果。

8. SubLength = j - i + 1;: 计算当前窗口的长度，即从索引 i 到 j 的元素数量。

9. result = result < SubLength ? result : SubLength;: 更新结果变量 result，如果当前窗口长度 SubLength 比已知的最小长度还要小，则用 SubLength 替换 result。

10. sum -= nums[i++];: 缩小窗口，从 sum 中减去 nums[i] 的值，并将左指针 i 向右移动一位，准备检查下一个可能的子数组。

11. }: 结束内部的 while 循环。

12. }: 结束外部的 for 循环。

13. return result == INT32_MAX ? 0 : result;: 最后，检查结果 result 是否仍然为初始值 INT32_MAX，如果是，则说明没有找到满足条件的子数组，返回 0；否则，返回找到的最短子数组长度 result。

1.3 扩展

题目原文：

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

输入：s1= "ab" s2 = "eidboaoo"
输出：false

题解：

class Solution {
public:bool checkInclusion(string s1, string s2) {sort(s1.begin(),s1.end());int left = 0;int right = s1.size();while(right <= s2.size()){string s3 = s2.substr(left , s1.size());sort(s3.begin(),s3.end());if(s3 == s1){return true;}left++;right++;}return false;}
};

思路：

1. 排序s1：首先对字符串s1中的字符进行排序。这样做的目的是为了后续可以方便地比较两个字符串的字符排列是否相同。

2. 双指针滑动窗口：使用两个指针left和right定义一个大小与s1相同的窗口，这个窗口将在s2上滑动。初始化时，left = 0，right = s1.size()。

3. 循环遍历s2：在循环中，窗口的右边界逐渐向右扩展，直到覆盖整个s2字符串。循环条件为right <= s2.size()。

4. 提取子串并排序：每次循环中，从s2中提取大小与s1相同的子串s3（由索引left到left + s1.size() - 1的字符组成），并对这个子串进行排序。

5. 比较排序后的子串：将排序后的子串s3与排序后的s1进行比较。如果两者相等，说明当前窗口内的字符排列与s1相同，函数返回true。

6. 窗口滑动：如果当前窗口内的字符排列与s1不同，则窗口向右滑动一位：增加left和right的值各1，继续下一次循环检查新的子串。

7. 循环结束处理：如果循环结束后都没有找到匹配的子串，说明s2中不存在s1的排列作为子串，函数返回false。