目录

1、滑动窗口算法

1.1 核心概念

1.2 基本步骤

1.3 应用场景

1.4 优势

2. leetcode 209 长度最小子数组

暴力解题思路：

滑动窗口思路：

3、无重复字符的最长子串

暴力解题思路： 

滑动窗口思路：

---

1、滑动窗口算法

        滑动窗口算法是一种在处理数组、字符串或其他序列数据结构时非常有用的技巧，特别适用于寻找特定条件的连续子序列问题。这种算法通过维护一个可变的“窗口”，在序列上滑动来高效地解决问题。

        使用滑动窗口通常会用到双指针，我们在前面也讲解过双指针，可以参考双指针算法篇：两数之和 、三数之和

1.1 核心概念

窗口：想象一个可以在序列上左右移动的窗口，窗口内的元素是我们关注的对象。

双指针：通常使用两个指针（左指针和右指针）来表示窗口的边界。左指针代表窗口的起始位置，右指针代表窗口的结束位置。

动态调整：根据问题需求，窗口的大小可能固定也可能变化，通过移动左右指针来调整窗口覆盖的范围。

1.2 基本步骤

1. 初始化：设置左指针 left 和右指针 right 初始位置，通常从序列的起始位置开始。根据问题可能还需要初始化一些状态变量，比如窗口内元素的和、计数器等。
2. 扩展窗口：逐步将右指针向右移动，每次移动都检查新增元素是否满足问题条件，同时更新窗口内的相关信息（如总和、最大值、最小值等）。
3. 收缩窗口：当窗口满足某个终止条件时（如总和达到了目标值、找到了所需子序列等），开始考虑缩小窗口。通过移动左指针来排除窗口左侧的元素，同时保持窗口内信息的更新。
4. 重复步骤2和3：在序列未完全探索之前，持续执行扩展和收缩窗口的操作。
5. 结果处理：根据问题需求，在算法执行过程中或结束后处理并返回最终结果。

1.3 应用场景

最大/最小子数组和：找到数组中和最大的（或最小的）连续子数组。

无重复字符的最长子串：在字符串中寻找不含重复字符的最长子串。

子数组问题：如找到和大于等于特定值的最小子数组长度。

字符串匹配：如寻找包含所有字母的最小子串等。

1.4 优势

效率：将原本可能需要嵌套循环的问题简化为单层循环，显著提高了算法的时间复杂度，通常达到O(n)级别。

灵活性：适用于多种类型的问题，只需适当调整窗口的扩展和收缩条件。

2. leetcode 209 长度最小子数组

题目描述

给定一个含有 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. 双重循环：外层循环遍历数组的每个起始位置，内层循环尝试以该位置为起点的所有可能的子数组。
2. 计算子数组和：对每个子数组，累加其元素和。
3. 判断与更新：如果当前子数组的和达到或超过目标值，就比较并更新最小长度。
4. 结果处理：如果最小长度仍为初始值（即大于数组长度），说明没有找到符合条件的子数组，返回0；否则返回找到的最小长度。

代码示例：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();if (n == 0) return 0;// 初始化结果为不可能的情况，即比数组长度还大1int minLength = n + 1;// 双重循环，枚举所有子数组for (int start = 0; start < n; ++start) {int sum = 0;for (int end = start; end < n; ++end) {sum += nums[end]; // 计算当前子数组的和// 如果当前子数组和大于等于目标值，更新最短长度if (sum >= target) {minLength = min(minLength, end - start + 1);break; // 找到一个满足条件的子数组后，提前结束内层循环}}}// 如果没有找到满足条件的子数组，返回0；否则返回找到的最短长度return minLength == n + 1 ? 0 : minLength;}
};

时间复杂度较高，为O(n^2)，在数据规模较大时效率低下，不适用于性能敏感的场景。相比滑动窗口算法的线性时间复杂度O(n)，暴力解法在效率上明显不足。

暴力解法虽然思路简单，但是效率低下，在这个题目要求下会超时，暴力是将所有子数组列举一遍，但是比如start到end间的数据已经计算过一次了，再计算就没有必要了，所以只需要在sum中减去nums[left]，left++即可。

滑动窗口思路：

1. 初始化:

   • 初始化两个指针 left 和 right，均从0开始。
   • 初始化 sum（当前窗口内元素的和）为0，ret（记录满足条件的最短子数组长度，默认极大值INT_MAX）。

2. 双指针遍历:

   • 使用 right 指针遍历数组，将新元素加入窗口和 sum 中。（进窗口）

3. 窗口内求解:（循环）

   • 当窗口内元素和 sum 大于等于目标值 target 时：
     • 更新 ret 的值为当前子数组长度（right-left+1）和原 ret 中的较小值。
     • 然后从窗口（即从 sum 中）移除左侧元素（nums[left]），并将 left 指针右移一位，继续寻找可能更小的满足条件的子数组。（出窗口）

4. 循环结束处理:

   • 遍历结束后，若 ret 仍为初始值 INT_MAX，说明没有找到符合条件的子数组，返回0；否则返回 ret。

代码示例： 

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int sum=0;int ret=INT_MAX;for(int left=0,right=0;right<nums.size();right++){sum+=nums[right];while(sum>=target){ret=min(ret,right-left+1);sum-=nums[left];left++;}}return ret==INT_MAX?0:ret;}
};

滑动窗口简化了循环，时间效率上提示了很多，不会超时。

3、无重复字符的最长子串

题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

 示例：

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。

暴力解题思路： 

1. 双重循环：外层循环遍历字符串的每个字符作为子串的起始点，内层循环尝试以该字符为起点的后续所有字符作为子串的一部分。
2. 无重复检查：使用unordered_set来存储当前子串中的字符，以检查是否有重复。一旦发现重复字符，立即停止对该起始位置的进一步扩展，并检查下一个起始位置。
3. 更新最大长度：在每次内循环结束时，用当前无重复子串的长度更新最长无重复子串的长度。

代码示例：

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.length();int maxLength = 0; // 用于记录最长无重复子串的长度// 枚举所有可能的子串起始位置for (int i = 0; i < n; ++i) {unordered_set<char> charSet; // 用于检查当前子串是否有重复字符int uniqueLength = 0; // 记录当前子串的长度// 枚举以i为起始的子串的结束位置jfor (int j = i; j < n; ++j) {// 如果当前字符不在charSet中，说明是新的唯一字符if (charSet.find(s[j]) == charSet.end()) {charSet.insert(s[j]);uniqueLength++; // 子串长度增加} else {// 如果当前字符已经出现过，则停止当前子串的检查break;}}// 更新最大无重复子串长度maxLength = max(maxLength, uniqueLength);}return maxLength;}
};

暴力解法虽然勉强跑过了，但还是效率比较低。

滑动窗口思路：

1. 初始化:

   • 定义变量 ret 用来记录最长子串长度，初始化为0。
   • 获取字符串长度 n。
   • 初始化一个大小为128的整型数组 hash 用于记录ASCII表中每个字符出现的次数（假设字符串只包含ASCII字符）。

2. 双指针遍历:

   • 使用 left 和 right 分别作为窗口的左右边界，初始时都指向字符串的起始位置。
   • right 向右移动，遍历整个字符串。

3. 字符计数与窗口调整:

   • 每遇到一个字符，就在 hash 表中对应字符的计数加一。（进窗口）hash[s[right]]++;
   • 当 hash[s[right]] 大于1(循环)，说明当前字符在窗口内有重复，这时需要移动 left 指针来缩小窗口，直到窗口内没有重复字符。同时，hash[s[left]] - -，并将 left 向右移动。（出窗口）

4. 更新最长子串长度:

   在每次窗口调整后（即窗口内无重复字符时），用 right-left+1 计算当前无重复子串的长度，并用 max() 函数更新全局最长子串长度 ret。

5. 返回结果:

   遍历结束后，返回最长无重复字符子串的长度 ret。

代码示例：

class Solution {
public:int lengthOfLongestSubstring(string s) {int ret=0;int n=s.size();int hash[128]{0};for(int left=0,right=0;right<n;right++){hash[s[right]]++;while(hash[s[right]]>1){hash[s[left]]--;left++;}ret=max(ret,right-left+1);}return ret;}
};

滑动窗口简化了循环，通过巧妙地控制窗口的扩张与收缩来高效地找到满足条件的最长子串，相较于暴力解法，其时间复杂度大大降低至O(n)。

两者可能相似，取决于具体实现。暴力解法可能会使用额外的数据结构（如哈希表）来辅助检查，滑动窗口同样可能使用哈希表来跟踪窗口内的元素，但整体上，滑动窗口的空间复杂度一般更为可控且高效，因为它不需要存储所有可能的子序列。

暴力解法：通常具有较高的时间复杂度，例如在解决“寻找字符串中无重复字符的最长子串”问题时，暴力解法的时间复杂度为O(n^2)，因为它需要对每个子串进行检查，而子串数量是n(n+1)/2。

暴力解法在数据规模较小时可能尚可接受，但在面对大规模数据集时，其效率低下，难以在有限时间内得到结果。

滑动窗口：时间复杂度通常为O(n)，这是因为滑动窗口算法只需要遍历一次输入序列。通过动态调整窗口的大小，它能够高效地找到满足条件的子序列，避免了冗余的检查。