当前位置：首页 > article >正文

【优选算法篇】滑动窗口的艺术：如何动态调整子区间解决复杂问题（中篇）

article 2024/12/3 3:19:55

文章目录

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++算法感兴趣的朋友，让我们一起进步！

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

引言：通过上篇文章带大家简单了解“滑动窗口算法”，小试牛刀。接下来将让大家感受一下滑动窗口在解题中的更多妙处。

滑动窗口算法在面试中的重要性不仅在于它是一种高效解决问题的方法，更因为它能够系统化评估候选人在算法设计、优化、实现和调试等多个维度的能力。掌握滑动窗口的核心思想和进阶技巧，对于候选人在算法面试中脱颖而出至关重要。

"C++滑动窗口算法：高效解决子数组与子串问题的利器"

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

1.1 滑动窗口基本概念

滑动窗口的“窗口”指的是一个数组或字符串的连续子集。在算法中，我们通过两个指针（通常为左指针和右指针）来表示这个窗口。窗口的大小可以是固定的，也可以是动态变化的，通常依据具体问题的需求来调整。

1.2 基本应用场景

1.2.1 数据流问题

滑动窗口还常用于处理实时数据流中的问题，例如：

计算实时数据流的平均值：给定一个数据流，在每一时刻计算窗口内数据的平均值。
流式计算问题：对实时数据流应用滑动窗口来动态计算所需的统计量，如最大值、最小值、和等。

1.2.2 变长滑动窗口

当滑动窗口的大小不是固定时，窗口的大小会动态变化。通过扩展右边界，直到满足特定条件，再通过收缩左边界以保持窗口内的数据符合要求。

例如，滑动窗口的元素和大于某个目标值时收缩窗口。

1.2.3 求最大值/最小值滑动窗口

在一些问题中，我们需要在给定大小的滑动窗口中计算最大值或最小值。这类问题在数据流处理、实时监控等场景中非常常见。

滑动窗口中的最大值：给定一个数组，求出每个大小为k的窗口的最大值。

1.2.4 字符计数问题

滑动窗口可以用于解决在一定范围内对字符或元素计数的问题。例如，给定一个字符串和一个字符集，找出每个字符在滑动窗口中的出现频率。

字符覆盖问题：在一个字符串中，找出包含目标字符集所有字符的最小子串。

2. 题目1：将 x 减小到 0 的最小操作数

题目链接：1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

题目描述：

2.1 算法思路：

2.1.1 详细步骤

计算总和：首先，计算数组 nums 的总和 sum。我们希望通过从两端移除元素使得剩余的和为 x。

所以我们需要找到一个子数组，其和为 sum - x。这个子数组的长度越长，表示我们从两端删除的元素越少，从而操作次数最少。
目标计算：目标和 target = sum - x。我们需要通过滑动窗口的方式，找到和为 target 的最长子数组。因为一旦找到这个子数组，剩下的部分就是最小操作数所需删除的元素。
滑动窗口：
- 使用两个指针 left 和 right，通过移动 right 来扩展窗口，计算当前窗口的和。
- 如果当前窗口的和大于 target，则通过移动 left 来缩小窗口，直到窗口的和小于或等于 target。
- 如果当前窗口的和恰好等于 target，则更新最大子数组长度。
结果计算：
- 最终结果就是 n - maxLength，其中 n 是数组的大小，maxLength 是找到的和为 target 的最长子数组的长度。

2.2 示例代码：

class Solution 
{
public:
    int minOperations(vector<int>& nums, int x)
    {
        int n = nums.size(), sum = 0, ret = -1;
        
        // 计算数组总和
        for (auto m : nums)
        {
            sum += m;
        }

        // 计算目标和 (sum - x)
        int target = sum - x;

        // 如果目标和小于 0，则无法通过任何方式将 x 减到 0
        if (target < 0) return -1;

        int tmp = 0;
        
        // 使用滑动窗口查找最大长度的子数组，其和为 target
        for (int left = 0, right = 0; right < n; right++)
        {
            tmp += nums[right];  // 将当前右端元素加入窗口

            // 如果窗口和大于 target，则通过移动左边界缩小窗口
            while (left < n && tmp > target)
            {
                tmp -= nums[left++];
            }

            // 如果窗口和正好等于 target，更新最大子数组长度
            if (tmp == target)
            {
                ret = max(ret, right - left + 1);
            }
        }

        // 如果未找到合适的子数组，返回 -1
        return ret == -1 ? -1 : n - ret; 
    }
};

2.2.1 代码流程

总和计算：遍历 nums 数组，计算其总和 sum。
目标计算：将目标值 target 设为 sum - x，如果目标值小于 0，则无法通过任何操作使 x 减小为 0，直接返回 -1。
滑动窗口：
- 使用两个指针 left 和 right，当 right 向右移动时，我们不断增加窗口的和 tmp。
- 当和超过目标值 target 时，通过移动 left 指针来缩小窗口，直到窗口的和小于或等于 target。
- 如果窗口的和正好等于 target，则记录当前子数组的长度，并更新 ret 变量。
返回结果：最终结果是 n - ret，即从两端删除的元素个数。如果没有找到合适的子数组，返回 -1。

2.2.2 示例

假设输入数组 nums = [1, 1, 4, 2, 3] 和 x = 5：

计算总和：sum = 1 + 1 + 4 + 2 + 3 = 11。
目标和：target = 11 - 5 = 6。
滑动窗口：
- 遍历时，查找和为 6 的子数组。窗口 [4, 2] 的和为 6，长度为 2。
返回结果：最小操作数是 5 - 2 = 3，因为从两端移除元素后的剩余部分是 [4, 2]。

最终结果为 3。

2.3 时间与空间复杂度

2.3.1 时间复杂度

计算总和：遍历数组一次，时间复杂度为 O(n)。
滑动窗口：左右指针最多各自移动 n 次，总的时间复杂度为 O(n)。
因此，总的时间复杂度是 O(n)。

2.3.2 空间复杂度

只使用了常数空间来存储一些变量，因此空间复杂度是 O(1)。

2.4 补充（可看可不看）

2.4.1 暴力解法

int minOperations(vector<int>& nums, int x)
{
    int n = nums.size();
    int minOps = INT_MAX; // 初始化最小操作数为无穷大

    // 计算前缀和
    vector<int> prefixSum(n + 1, 0);
    for (int i = 0; i < n; ++i)
    {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    // 暴力枚举两端的移除组合
    for (int left = 0; left <= n; ++left)
    {
        for (int right = 0; right <= n - left; ++right)
        {
            int leftSum = prefixSum[left];
            int rightSum = prefixSum[n] - prefixSum[n - right];
            if (leftSum + rightSum == x)
            {
                minOps = min(minOps, left + right);
            }
        }
    }

    // 如果没有找到满足条件的组合，返回 -1
    return minOps == INT_MAX ? -1 : minOps;
}

代码说明

前缀和数组：
- 构建 prefixSum 数组，计算出从左端开始的累积和，这样可以快速得到左端的和。
- 使用 prefixSum[n]−prefixSum[n−right] 快速计算右端的累积和。
双重循环枚举：
- 外层循环遍历左端移除的元素数 left。
- 内层循环遍历右端移除的元素数 right。
- 检查两端移除的和是否等于 x，如果满足条件，则更新最小操作数。
返回结果：
- 如果遍历完所有组合后仍未找到满足条件的情况，返回 -1。
- 如果找到，返回记录的最小操作数。

2.4.2 时间与空间复杂度

时间复杂度

前缀和构建：O(n)。
双重循环：最多 O(n^2)。
总时间复杂度：O(n^2)。

空间复杂度

前缀和数组需要 O(n)的额外空间。

2.5 总结

通过滑动窗口，我们可以高效地找到和为 sum - x 的最大子数组，并计算出最小操作次数。这种方法的时间复杂度是线性的 O(n)，非常适合处理大规模数据。

3. 题目2：水果成篮

题目链接：904. 水果成篮 - 力扣（LeetCode）

题目描述：

补充：

3.1 算法思路：

3.1.1 使用滑动窗口

滑动窗口是维护一个区间 [left, right] 的方法，通过动态调整窗口的左右边界来满足题目要求。在本题中：

窗口内的水果种类数不能超过 2。
窗口长度即为可以采摘的最大连续水果数。

3.1.2 哈希表记录窗口内水果数量

利用哈希表 unordered_map<int, int> hash：

键（key）：水果的种类。
值（value）：该种水果在窗口中的出现次数。

3.2 示例代码：

class Solution 
{
public:
    int totalFruit(vector<int>& fruits)
    {
        // 用于记录窗口中每种水果的出现次数
        unordered_map<int, int> hash;
        int ret = 0; // 用于存储当前能够采摘的最大连续水果数

        // 定义滑动窗口的左右边界
        for (int left = 0, right = 0; right < fruits.size(); right++)
        {
            // 将右边界的水果加入窗口，增加其计数
            hash[fruits[right]]++;

            // 如果窗口内水果种类超过两种，则开始缩小窗口
            while (hash.size() > 2)
            {
                // 减少左边界水果的计数
                hash[fruits[left]]--;

                // 如果某种水果的计数变为 0，移除该水果种类
                if (hash[fruits[left]] == 0)
                    hash.erase(fruits[left]);

                // 移动左边界
                left++;
            }

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

        // 返回最大长度
        return ret;
    }
};

3.2.1 代码流程解析

1. 初始化

使用一个哈希表 hash 记录窗口中每种水果的数量。
定义两个指针 left 和 right 表示滑动窗口的左右边界。
变量 ret 用来记录当前窗口的最大长度。

2. 遍历数组

right 遍历水果数组 fruits，每次将 fruits[right] 加入窗口，并在 hash 中更新对应水果的数量。

3. 调整窗口

如果 hash.size()（窗口中的水果种类数）大于 2，说明窗口不满足条件，开始通过移动 left 缩小窗口：
- 减少 fruits[left] 的计数。
- 如果计数变为 0，从哈希表中移除该水果种类。
- 将 left 向右移动一位。

4. 更新结果

在每次调整窗口后，计算当前窗口长度为 right - left + 1，并更新 ret。

5. 返回结果

遍历完成后，返回记录的最大值 ret。

3.2.2 流程图解

以输入 fruits = [1, 2, 1, 2, 3] 为例，展示滑动窗口的动态变化：

初始状态

left = 0, right = 0, hash = {}, ret = 0。

Step 1: right = 0

新增水果 1：
- hash = {1: 1}。
窗口有效，更新结果：
- ret = max(0, 0 - 0 + 1) = 1。

窗口：[1]
种类：{1}
当前最大长度：1

Step 2: right = 1

新增水果 2：
- hash = {1: 1, 2: 1}。
窗口有效，更新结果：
- ret = max(1, 1 - 0 + 1) = 2。

窗口：[1, 2]
种类：{1, 2}
当前最大长度：2

Step 3: right = 2

新增水果 1：
- hash = {1: 2, 2: 1}。
窗口有效，更新结果：
- ret = max(2, 2 - 0 + 1) = 3。

窗口：[1, 2, 1]
种类：{1, 2}
当前最大长度：3

Step 4: right = 3

新增水果 2：
- hash = {1: 2, 2: 2}。
窗口有效，更新结果：
- ret = max(3, 3 - 0 + 1) = 4。

窗口：[1, 2, 1, 2]
种类：{1, 2}
当前最大长度：4

Step 5: right = 4

新增水果 3：
- hash = {1: 2, 2: 2, 3: 1}。
窗口无效，开始调整：
- 移除 1，hash = {1: 1, 2: 2, 3: 1}。
- 再次移除 1，hash = {2: 2, 3: 1}。
- left = 2。
窗口有效，更新结果：
- ret = max(4, 4 - 2 + 1) = 4。

窗口：[2, 1, 3]
种类：{2, 3}
当前最大长度：4

最终结果

遍历结束后，最大长度为 ret = 4。

动态过程图（用字符表示）

3.3 时间与空间复杂度

3.3.1 时间复杂度

窗口扩展（右指针遍历）： 每个元素被遍历一次，时间复杂度为 O(n)。
窗口收缩（左指针移动）： 每个元素最多被收缩一次，时间复杂度为 O(n)。
总时间复杂度：O(n)。

3.3.2 空间复杂度

使用了一个哈希表，最多存储 2 个水果种类，空间复杂度为 O(1)。

3.4 补充（可看可不看）

3.4.1 暴力解法

class Solution 
{
public:
    int totalFruit(vector<int>& fruits) 
    {
        int n = fruits.size();
        int maxLength = 0;

        for (int i = 0; i < n; ++i) 
        {
            unordered_set<int> basket; // 用于存储当前区间的水果种类
            int currentLength = 0;

            for (int j = i; j < n; ++j) 
            {
                basket.insert(fruits[j]); // 将当前水果加入集合
                if (basket.size() > 2) // 超过两种水果，停止继续扩展
                    break;

                currentLength++;
                maxLength = max(maxLength, currentLength); // 更新最大长度
            }
        }

        return maxLength;
    }
};

代码逻辑解析：

双层循环：
- 外层循环以 i 为起点，遍历数组。
- 内层循环以 j 为终点，扩展当前子区间。
集合维护水果种类：
- 使用 unordered_set<int> 存储当前区间内的水果种类。
- 每次添加水果时，检查集合大小是否超过 2。
长度更新：
- 如果当前区间满足条件（basket.size() <= 2），计算区间长度并更新 maxLength。