【优选算法篇】一文读懂滑动窗口：动态调整范围的算法利器（上篇）

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！ 👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！ 🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++算法感兴趣的朋友，让我们一起进步！

1. C++ 滑动窗口算法详解

1.1 滑动窗口算法重要性

滑动窗口（Sliding Window）是一种高效的算法思想，广泛应用于数组和字符串问题，特别是涉及子数组、子字符串、窗口内统计等场景。它的重要性在于：

1. 提升效率：通过动态调整窗口范围，避免暴力枚举所有可能的子区间，从而将时间复杂度从 O(N^2) 或更高优化到 O(N)。
2. 简化逻辑：滑动窗口提供了一个统一的框架，可以直观地处理许多问题，如最大/最小子数组和、子数组个数统计等。
3. 实际应用广泛：在数据流、字符串处理、窗口内最值计算等领域具有广泛应用。

本文将通过简单的例题来讲解“同向双指针”算法的不同应用，以及如何在 C++ 中实现。同向双指针也称为“滑动窗口”。

1.2 什么是滑动窗口？

滑动窗口是一种动态调整区间范围的算法。它将问题中的“窗口”定义为一段连续的子数组或子字符串，并通过增加或减少窗口的左右边界来动态计算结果。窗口的范围会随着问题的需求而“滑动”，从而优化问题求解过程。

窗口的两种典型类型：

1. 固定窗口：窗口大小固定，通过滑动计算覆盖不同的区间。
2. 可变窗口：窗口大小可变，根据条件动态调整范围。

1.3 核心思想

滑动窗口的核心思想是：

通过一对指针（通常为左右指针 left 和 right），定义一个“窗口”，然后在窗口内进行动态计算。

实现步骤：

1. 初始化窗口：定义窗口的起点（left）和终点（right），一般初始为 0。
2. 扩展窗口：通过移动 right 指针扩展窗口，直到窗口内满足特定条件。
3. 缩小窗口：当窗口满足条件时，移动 left 指针缩小窗口，同时更新结果。
4. 重复上述过程：直到 right 指针遍历完整个数组或字符串。

关键点：

• 动态调整窗口的范围。
• 记录窗口内的状态（如当前和、频率计数等）。
• 根据问题需求判断何时更新结果。

1.4 滑动窗口的应用场景

1. 求解固定长度的子数组/子字符串问题：
   • 如最大或最小子数组和，最长不重复子字符串。
2. 求解动态条件的区间问题：
   • 如满足条件的最短子数组，窗口内的元素个数统计。
3. 在线算法和数据流问题：
   • 滑动窗口可以在数据流中实时计算指标。

2. 滑动窗口的逻辑可以归纳为以下模板：

int slidingWindow(vector<int>& nums, int target) { int left = 0, current_sum = 0, result = INT_MAX; for (int right = 0; right < nums.size(); ++right) { current_sum += nums[right]; // 扩展窗口 while (current_sum >= target)// 符合条件，尝试缩小窗口 { result = min(result, right - left + 1); current_sum -= nums[left++]; // 移动左边界，缩小窗口 } } return result == INT_MAX ? 0 : result; // 如果没找到满足条件的子数组返回 0 }

3. 题目1：长度最小的子数组

题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

题目描述：

3.1 算法思路：

3.1.1 初始化变量：

• start 和 end：
  • 两个指针分别表示滑动窗口的左边界和右边界。
  • start 用于缩小窗口，end 用于扩展窗口。
• ret：
  • 记录满足条件的最小子数组长度，初始化为 INT_MAX（一个很大的值）。
• sum：
  • 维护当前窗口内元素的总和。

3.1.2 扩展窗口：

通过 for 循环移动右边界 end：

• 每次加入 nums[end] 到 sum 中，表示将当前元素纳入窗口。
• 目的：不断扩大窗口直到窗口内的和满足条件。

3.1.3 缩小窗口：

当 sum >= target 时，尝试通过移动 start 来缩小窗口：

• 更新 ret 为当前窗口的长度：end - start + 1。
• 从窗口中移除 nums[start]，并将 start 向右移动。

3.1.4 返回结果：

• 如果 ret 仍是 INT_MAX，说明不存在满足条件的子数组，返回 0。
• 否则返回 ret，即满足条件的最小子数组长度。

滑动窗口的核心逻辑

• 扩展窗口：通过右移 end 指针，确保当前窗口尽可能覆盖更多元素。
• 缩小窗口：当条件满足（sum >= target）时，通过右移 start 指针缩小窗口，尽量寻找更短的子数组。

3.2 示例代码：

class Solution 
{
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
        // 定义两个指针 start 和 end，分别表示窗口的左边界和右边界
        // ret 表示满足条件的最小子数组长度，初始化为无穷大
        // sum 用于记录窗口内元素的总和
        int start = 0, end = 0, ret = INT_MAX, sum = 0;
        
        // 遍历数组，右边界不断向右扩展
        for (; end < nums.size(); end++) 
        {
            sum += nums[end]; // 将当前元素加入窗口
            // 如果窗口内的和大于等于 target，则尝试缩小窗口
            while (sum >= target) 
            {
                // 更新最小长度为当前窗口大小
                ret = min(ret, end - start + 1);
                
                // 将窗口左边界的元素移出窗口，并右移左边界
                sum -= nums[start++];
            }
        }
        // 如果 ret 仍为初始值，说明不存在满足条件的子数组，返回 0
        return ret == INT_MAX ? 0 : ret;
    }
};

3.2.1 执行过程解析

以输入 nums = [2, 3, 1, 2, 4, 3], target = 7 为例，运行过程如下：

最终结果输出 2。

3.3 时间与空间复杂度

1. 时间复杂度：
   • 每个元素最多被访问两次（一次被加入窗口，一次被移出窗口），因此时间复杂度为 O(N)。
2. 空间复杂度：
   • 使用常数个变量，空间复杂度为 O(1)。

3.4 补充（可看可不看）

3.4.1 时间复杂度为 O(N^3) 的代码

通过三层嵌套循环暴力求解。

int minSubArrayLen_O_N3(int target, vector<int>& nums) {
    int n = nums.size();
    int minLen = INT_MAX;

    for (int start = 0; start < n; ++start) {
        for (int end = start; end < n; ++end) {
            int sum = 0;
            for (int k = start; k <= end; ++k) { // 计算子数组的和
                sum += nums[k];
            }
            if (sum >= target) {
                minLen = min(minLen, end - start + 1);
            }
        }
    }
    return minLen == INT_MAX ? 0 : minLen;
}

3.4.2 时间复杂度为 O(N^2) 的代码

通过两层嵌套循环，内层循环直接累加子数组和，减少了第三层循环。

int minSubArrayLen_O_N2(int target, vector<int>& nums) {
    int n = nums.size();
    int minLen = INT_MAX;

    for (int start = 0; start < n; ++start) {
        int sum = 0; // 初始化子数组的和
        for (int end = start; end < n; ++end) {
            sum += nums[end]; // 累加子数组的和
            if (sum >= target) {
                minLen = min(minLen, end - start + 1);
                break; // 找到满足条件的最短子数组后停止当前循环
            }
        }
    }
    return minLen == INT_MAX ? 0 : minLen;
}

3.5 总结：

这段代码很好地体现了滑动窗口的思想：

• 动态调整范围：右边扩展窗口，左边缩小窗口。
• 实时维护结果：在条件满足时更新最优解。

这是解决子数组问题的高效通用方法，非常适合用来练习和掌握滑动窗口技巧。

4. 题目2：无重复字符的最长子串

题目链接：3. 无重复字符的最长子串 - 力扣（LeetCode）

题目描述：

4.1 算法思路：

1. 滑动窗口技术：
   • 我们使用两个指针 left 和 right，它们分别表示当前窗口的左边界和右边界。窗口内的字符是连续的，并且不包含重复字符。
   • 右指针 right 会从左到右遍历字符串，扩展窗口；而左指针 left 会根据需要收缩窗口，以确保窗口内没有重复字符。
2. 哈希表（或数组）用于存储字符出现的次数：
   • 使用一个大小为128的数组 hash 来记录窗口内字符的出现次数。字符的ASCII值作为数组的索引。
   • 当右指针移动到新的字符时，我们将该字符的计数增加；如果该字符已经在窗口中出现（即计数大于1），我们移动左指针，直到窗口内没有重复字符。
3. 更新最大长度：
   • 每次右指针移动时，窗口内的字符都是唯一的。我们计算当前窗口的长度 right - left + 1，并将其与已知的最大长度进行比较，更新最大值。

4.1.1 算法流程：

1. 初始化哈希表 hash 和变量 ret 用来记录最长子串的长度。
2. 使用两个指针 left 和 right 来表示窗口的边界。右指针从 0 开始，逐步向右移动，左指针在有重复字符时向右移动以收缩窗口。
3. 在每一步，更新最大子串长度。

4.2 示例代码：

class Solution 
{
public:
    int lengthOfLongestSubstring(string s)
    {
        int hash[128] = {0}, n = s.size(), ret = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
            hash[s[right]]++; // 将当前字符加入窗口
            while(hash[s[right]] > 1) // 如果窗口内有重复字符
            {
                hash[s[left++]]--; // 收缩窗口，移动左边界
            }
            ret = max(ret, right - left + 1); // 计算当前窗口的长度，更新最长长度
        }
        return ret;
    }
};

4.2.1 运行过程示例

假设输入字符串为 "abcabcbb"，解析如下：

最终结果：最长无重复子串长度为 3，对应子串为 "abc"。

4.2.2 动态变化解析

1. 扩展窗口：每次移动 right，尝试将字符加入窗口，同时更新 hash 数组记录频次。
2. 收缩窗口：如果窗口中出现重复字符（hash[s[right]] > 1），则移动 left 直到窗口中没有重复字符。
3. 更新结果：每次窗口合法时，计算窗口长度 right - left + 1，并更新 ret。

4.3 时间与空间复杂度

1. 时间复杂度：O(n)，字符串中每个字符最多被 right 和 left 访问一次。
2. 空间复杂度：O(1)，hash 数组大小固定。

4.4 补充（个人觉得下面的实例更好理解）

示例代码：

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        int hash[128] = { 0 }; // 使用数组来模拟哈希表，字符集为ASCII，最多128种字符
        int left = 0, right = 0, n = s.size(); // left和right是滑动窗口的左右边界，n是字符串的长度
        int ret = 0; // 用于记录最长无重复子串的长度

        while (right < n) // 遍历字符串，右指针扩展窗口
        { 
            if (hash[s[right]] == 0) // 当前字符没有重复
            {
                hash[s[right]]++; // 将该字符标记为出现过
                right++; // 右指针右移
                ret = max(ret, right - left); // 更新最大长度
            }
            else
            {
                hash[s[left]]--; // 左指针右移，移除字符
                left++; // 缩小窗口，直到窗口内无重复字符
            }
        }
        return ret; // 返回最长无重复子串的长度
    }
};

4.4.1 详细解析：

1. int hash[128] = { 0 };
   • 这里使用一个数组 hash 来模拟哈希表，其中 hash[i] 表示字符 i 在当前窗口内出现的次数。由于题目中字符串只有ASCII字符（最多128种字符），因此我们可以使用一个长度为128的数组来表示所有字符的出现情况。
   • 数组初始化为 0，表示每个字符的初始出现次数为 0。
2. int left = 0, right = 0, n = s.size();
   • left 和 right 是滑动窗口的左右边界，初始时都指向字符串的起始位置。
   • n 是字符串的长度，用来限制 right 指针的范围。
3. int ret = 0;
   • ret 用来记录最大无重复子串的长度。
4. while (right < n)
   • 这个循环遍历整个字符串。right 指针在循环中会逐渐向右扩展，直到遍历完整个字符串。
5. if (hash[s[right]] == 0)
   • 如果当前字符 s[right] 在窗口内没有重复（即 hash[s[right]] == 0），我们可以安全地将其加入到窗口中。
   • hash[s[right]]++ 更新该字符在窗口中的出现次数，并且将 right 指针向右移动，扩展窗口。
   • ret = max(ret, right - left) 更新 ret，即计算当前窗口的长度 right - left，并更新最大长度。
6. else
   • 如果当前字符 s[right] 已经存在于窗口内（即 hash[s[right]] > 0），我们需要移动 left 指针来缩小窗口，直到窗口中没有重复字符。
   • hash[s[left]]-- 表示移除字符 s[left]，然后将 left 右移。
7. return ret;
   • 循环结束后，返回记录的最大长度 ret。

4.4.2 时间与空间复杂度

时间复杂度：

• right 指针遍历了整个字符串一次，每次右移一次，最多有 n 次操作。
• 对于每个字符，left 指针最多右移一次，所以整体时间复杂度为 O(n)，其中 n 是字符串的长度。

空间复杂度：

• 使用一个大小为 128 的数组来记录字符的出现次数，因此空间复杂度是 O(1)，因为数组的大小是常数。

4.5 总结 ：

该算法利用滑动窗口技巧，通过动态扩展和收缩窗口，能够高效地找出字符串中最长的无重复子串。通过数组模拟哈希表，避免了频繁使用哈希表的开销，提高了性能。

5. 题目3：最大连续1的个数 |||

题目链接：1004. 最大连续1的个数 III - 力扣（LeetCode）

题目描述：

5.1 算法思路：

5.1.1 算法流程：

1. 定义两个指针 left 和 right，分别表示当前窗口的左右边界，用滑动窗口维护满足条件的最长子数组。
2. 遍历数组，用 right 向右扩展窗口，将每个元素加入窗口。
   • 如果当前元素为 0，则将计数器 zero 加 1，表示窗口内的 0 数量增加。
3. 如果窗口内的 0 的数量超过了允许的最大值 k，则通过移动 left 收缩窗口。
   • 如果移除的元素是 0，则将计数器 zero 减 1。
4. 每次窗口调整完毕后，更新当前窗口长度并尝试刷新最大值 ret。
5. 遍历结束后，ret 即为符合条件的最长子数组长度。

5.2 示例代码：

class Solution
{
public:
    int longestOnes(vector<int>& nums, int k)
    {
        int n = nums.size();       // 数组长度
        int zero = 0;              // 记录窗口中0的数量
        int ret = 0;               // 记录最长子数组的长度

        for (int left = 0, right = 0; right < n; right++)
        {
            if (nums[right] == 0)  // 扩展窗口时遇到0
                zero++;

            while (zero > k)       // 窗口中0的数量超过k时，需要收缩窗口
            {
                if (nums[left++] == 0) // 移动左边界，减少窗口内的0的数量
                    zero--;
            }

            ret = max(ret, right - left + 1); // 更新最长子数组长度
        }

        return ret;
    }
};

5.2.1 动态变化解析

假设输入 nums = [1,1,0,0,1,1,1,0,0,1]，k = 2。

最终结果：最长子数组长度为 8。

5.2.2 关键点解析

1. zero 计数器的作用：
   • 实时记录窗口内 0 的数量，便于判断是否超过允许值 k。
   • 超过 k 时，通过移动 left 缩小窗口。
2. 窗口合法性维护：
   • 窗口中允许最多包含 k 个 0，当超过时收缩窗口直到合法。
3. 最大值更新：
   • 每次扩展或调整窗口后，通过计算 right - left + 1 更新当前的最大子数组长度。

5.3 时间与空间复杂度

1. 时间复杂度：O(n)
   • left 和 right 指针各遍历数组一次，时间复杂度为线性。
2. 空间复杂度：O(1)
   • 只使用了常数空间存储变量。

5.4 补充（可看可不看）

class Solution 
{
public:
    int longestOnes(vector<int>& nums, int k)
    {
        int n = nums.size();
        int maxLength = 0;

        // 外层循环遍历每一个起点
        for (int left = 0; left < n; left++)
        {
            int flipCount = 0;
            // 右边界向右扩展
            for (int right = left; right < n; right++)
            {
                // 如果当前是0，翻转次数增加
                if (nums[right] == 0) 
                {
                    flipCount++;
                }
                // 如果翻转次数超过k，退出循环
                if (flipCount > k) 
                {
                    break;
                }
                // 更新最大长度
                maxLength = max(maxLength, right - left + 1);
            }
        }

        return maxLength;
    }
};

5.4.1 代码解析

1. 外层循环：从数组的每个位置 left 开始，尝试找到一个从 left 开始的子数组，包含最多 k 个 0 被翻转成 1。
2. 内层循环：在给定的起点 left 上，向右扩展窗口，直到遇到超过 k 个 0 需要翻转时，停止扩展。
3. 更新最大长度：每当扩展的子数组满足条件时，更新最大连续 1 的长度。
4. 返回最大长度：最终返回找到的最大长度。

5.4.2 时间与空间复杂度

时间复杂度

• 外层循环遍历每个起点，内层循环在最坏情况下遍历所有后续元素，所以时间复杂度为 O(n²)。

空间复杂度

• 由于只使用了常数空间来存储变量，因此空间复杂度为 O(1)。

5.4.3 总结：

这个暴力解法通过两层循环遍历所有可能的子数组，并计算翻转最多 k 个 0 后的最大连续 1 的长度。尽管该方法简单易懂，但由于时间复杂度为 O(n²)，在数组较大时效率较低，适合用作理解问题的起点。对于更高效的解决方案，可以考虑使用滑动窗口等优化算法。

5.5 总结：

这段代码利用滑动窗口解决了一个动态调整窗口范围的经典问题，核心是通过计数器 zero 维护窗口的合法性，并动态更新最长长度。算法高效、逻辑清晰，能够处理较大的输入规模。

6. 最后

通过上述「长度最小的子数组」、「无重复的最长子串」及「最大连续1的个数 |||」的例子，可以总结出滑动窗口算法的核心思想、应用场景和优化技巧。滑动窗口通过动态调整左右指针，在遍历数组时灵活地扩展和收缩窗口，避免了暴力解法中不必要的重复计算，使得许多问题的时间复杂度从 O(n^2) 或更高，优化到 O(n)。它在处理涉及连续子数组或子串的查找、统计、优化问题时，具有非常高的效率和空间优势，是解决此类问题的强大工具。

路虽远，行则将至；事虽难，做则必成

亲爱的读者们，下一篇文章再会！！！