深入浅出滑动窗口：如何高效计算乘积小于 K 的子数组

2026-02-08 11:35:50 0条评论 2次阅读 0人点赞

1 前言：不仅是解题，更是思维方式的升级
2 1. 问题描述：明确目标
3 2. 初步探索：为什么暴力解法行不通？
4 3. 核心突破：滑动窗口思想
5 4. 算法实现与代码详解
6 5. 深入理解：算法的正确性证明
7 6. 复杂度分析与对比
8 7. 扩展思考与变体
9 8. 总结

前言：不仅是解题，更是思维方式的升级

你是否在面试中遇到过这样的问题：给定一个数组，要求快速找出满足特定条件的所有连续子区间？或者，你是否在处理实际业务数据时，需要对流式数据进行实时的区间统计？

今天，我们将深入探讨一个经典的算法问题：“乘积小于 K 的子数组”。这不仅仅是一道刷题常见的算法题，更是掌握滑动窗口 这一核心算法思想的绝佳切入点。通过这篇文章，你将学会如何从暴力的 $O(N^2)$ 解法优雅地跳跃到 $O(N)$ 的线性解法，理解单调性在算法优化中的关键作用，并掌握一种能够迁移到字符串处理、流计算等众多领域的通用技巧。

我们将一起通过分析问题本质、拆解解题思路、编写健壮代码，最终彻底吃透这一技术难点。让我们开始吧！

—

1. 问题描述：明确目标

首先，让我们把问题定义得非常清晰。准确理解题目是解决问题的第一步。

核心任务：给定一个包含正整数的数组 INLINECODEc6393df3 和一个整数 INLINECODE0e2542be，我们的目标是统计该数组中乘积严格小于 k 的连续子数组的数量。

输入输出示例

为了建立直观的印象，我们先看两个具体的例子。

示例 1：常规情况

输入：INLINECODE254b7f3a, INLINECODE795a7327
输出：8
分析：我们需要找到所有乘积小于 100 的连续组合。

1. 长度为 1 的子数组：INLINECODEccab09dd, INLINECODE1294c8f9, INLINECODE632f28df, INLINECODEc339fac0 (乘积分别为 10, 5, 2, 6)。

2. 长度为 2 的子数组：INLINECODE4a1c6388 (乘积 50), INLINECODE3e96eb6f (乘积 10), [2, 6] (乘积 12)。

3. 长度为 3 的子数组：[5, 2, 6] (乘积 60)。

4. 注意：INLINECODE703587ca 的乘积是 100，因为它不严格小于 100，所以不算。同样的，INLINECODE913c25f1 乘积为 600，也不算。

5. 总计：4 + 3 + 1 = 8 个。

示例 2：边界情况

输入：INLINECODE83257280, INLINECODE76d02e87
输出：0
分析：题目指出数组元素均为正整数（最小为 1）。任何子数组的乘积至少也是 1。既然要求乘积小于 0，这在数学上显然是不可能的，因此直接返回 0。这个例子提醒我们，处理边界条件（如 $k \le 1$）至关重要。

—

2. 初步探索：为什么暴力解法行不通？

在接触高级技巧之前，通常我们先尝试最直观的方法，也就是暴力解法。这能帮助我们更好地理解问题的痛点。

暴力解法的逻辑

我们可以使用两层嵌套循环：

外层循环：遍历数组，确定子数组的起始位置 start。
内层循环：从 INLINECODE14d6ba67 开始向右扩展，计算累乘积，直到乘积不再小于 INLINECODE6f95753d 或到达数组末尾。

代码草稿（C++）

// 暴力解法示例
int numSubarrayProductLessThanK(vector& nums, int k) {
    int count = 0;
    int n = nums.size();
    
    // 外层循环：枚举起点
    for (int start = 0; start < n; start++) {
        int product = 1;
        // 内层循环：枚举终点并计算乘积
        for (int end = start; end = k) break;
            
            count++;
        }
    }
    return count;
}

性能瓶颈分析

虽然上述代码利用了“正整数乘积单调递增”的特性做了一些优化（提前 break），但在最坏情况下（例如数组全是 1，且 $k$ 很大），时间复杂度依然是 $O(N^2)$。

当 N 达到 $10^5$ 甚至更大时，$N^2$ 的操作量会导致超时。我们需要寻找一种只遍历数组一次或常数次的算法。

—

3. 核心突破：滑动窗口思想

为了优化性能，我们引入滑动窗口 算法。这是一种处理数组/字符串子区间问题的神器。

核心前提：单调性

为什么这道题能用滑动窗口？关键在于题目限定：数组元素都是正整数。

这意味着：

当窗口向右扩大时，乘积增加。
当窗口向左缩小（移除左侧元素）时，乘积减少。

这种单调性保证了我们不会陷入“移除了一个元素，乘积反而变大”的死胡同，从而可以安全地通过调整窗口边界来控制乘积的大小。

算法直觉

我们可以维护一个乘积始终小于 INLINECODEaeafd3ea 的窗口 INLINECODE2e6758a1。我们的目标是让 right 指针一路向右遍历数组。

扩展：将 nums[right] 加入当前乘积。
收缩：如果乘积超标（$\ge k$），我们就移动 left 指针，将窗口左侧元素剔除，不断缩小乘积，直到它重新满足条件。
统计：当窗口 [left, right] 满足条件时，我们如何统计数量？

统计技巧：以 right 为结尾

这是本题最容易产生困惑的地方：为什么 result += right - left + 1 是正确的？

想象一下，当前窗口是 INLINECODEf4e5b37d，且乘积 $5 \times 2 \times 6 = 60 < 100$。这意味着，只要在这个窗口内，以 INLINECODEa51e3ae4（即 6）结尾的任何连续子数组，其乘积一定小于 100（因为它是窗口乘积的因数）。

这些子数组分别是：

[6] (只包含自己)
[2, 6]
[5, 2, 6]

你看，只要确定了窗口的左边界 INLINECODE40e82af1，以当前 INLINECODE23a1c732 结尾的有效子数组数量就固定等于 窗口的长度 (INLINECODEb6fbdc4d)。通过 INLINECODE5e697208 指针的遍历，我们覆盖了所有可能的子数组结尾，从而统计出所有结果。

—

4. 算法实现与代码详解

基于上述思路，我们可以写出非常精简的 C++ 代码。请注意代码中的注释，它们解释了每一个关键步骤。

完整代码实现

class Solution {
public:
    int numSubarrayProductLessThanK(vector& nums, int k) {
        // 
        // 步骤 1：处理特殊边界情况
        // 如果 k = 1，乘积不可能 = k 
        // 而导致 left 指针越界（left > right）。
        if (k <= 1) return 0;
        
        int prod = 1;        // 当前窗口的乘积
        int result = 0;      // 最终结果
        int left = 0;        // 窗口左边界
        
        // 步骤 2：遍历右边界
        for (int right = 0; right = k) {
                prod /= nums[left]; // 除掉最左边的数
                left++;             // 左指针右移
            }
            
            // 步骤 3：统计结果
            // 此时 [left, right] 是一个满足条件的最小窗口吗？
            // 不，它是满足条件的最大窗口（包含 right）。
            // 因此，以 right 结尾的子数组个数就是窗口长度。
            result += right - left + 1;
        }
        
        return result;
    }
};

关键代码逻辑分解

if (k <= 1) return 0;

* 这是一个非常实用的防御性编程技巧。如果 $k=0$ 或 $k=1$，而数组元素至少为 1，那么 INLINECODE9cf4286c 初始为 1，一旦乘入元素就 $\ge 1$。此时 INLINECODEc73cc6f6 循环会试图通过除法来减小 INLINECODE23ec83b7，但 INLINECODEb5c9fda4 永远无法降到 1 以下（因为元素最小是 1）。这将导致 left 不断增加直到越界。提前返回避免了这种死循环。

while (prod >= k)

* 注意这里是 INLINECODE5e4b66a1 而不是 INLINECODE2556ced0。因为除掉一个 INLINECODEbe01317b 后，乘积可能依然很大（例如 INLINECODEd79664ee 中有很小的数 1，或者 nums[left] 本身很大），我们需要持续收缩直到条件满足。

result += right - left + 1

* 这是整个算法的灵魂。它利用了前缀和的思想，将“找出所有子数组”的问题转化为了“计算当前窗口包含多少个以前位置结尾的子数组”的问题。

—

5. 深入理解：算法的正确性证明

为了让你在面试中不仅能写出代码，还能清晰地解释思路，我们来简单证明一下为什么这个算法是正确的。

双指针的单向性

请注意，INLINECODEddfc8c15 和 INLINECODE660b3f2a 指针都只会向右移动，永远不会回退。

right 每次循环加 1。
INLINECODE9f9e761b 只在 INLINECODEd5d5867d 循环中增加。

由于两个指针最多遍历数组一次，整个算法的时间复杂度锁定在 $O(N)$。

覆盖完整性

算法是否遗漏了某些子数组？

我们枚举了每一个 right（从 0 到 n-1）。
对于固定的 INLINECODEc9cd10d4，我们找到了最大的 INLINECODEd86e2197，使得乘积 $\prod_{i=left}^{right} nums[i] < k$。
由于数组元素为正，对于任何 $start \in [left, right]$，乘积 $\prod_{i=start}^{right} nums[i]$ 一定也小于 $k$。
因此，以 right 结尾的所有合法子数组都被精确地计数了一次。

—

6. 复杂度分析与对比

让我们用数据说话，对比一下暴力解法和滑动窗口解法。

时间复杂度

暴力解法：$O(N^2)$。当 $N = 100,000$ 时，操作次数约为 50 亿次，在现代 CPU 上通常需要运行数秒甚至更久，远超通常的 1 秒时间限制。
滑动窗口：$O(N)$。INLINECODEd5de6856 走了 $N$ 步，INLINECODE17503d90 最多也走了 $N$ 步。总操作次数约为 $2N$。当 $N = 100,000$ 时，操作次数仅 20 万次，几乎瞬间完成。

空间复杂度

两者均为 $O(1)$。我们只使用了几个整型变量（INLINECODEb072c7da, INLINECODEbf01b3a0, INLINECODE1542db9d, INLINECODE34039bd0），没有开辟额外的数组或哈希表。这是一种非常高效的内存使用方式。

—

7. 扩展思考与变体

掌握了滑动窗口后，你可以尝试解决以下类似问题，巩固技能：

和大于等于 target 的最短子数组：

* 这里的条件从“乘积”变成了“和”，从“小于”变成了“大于等于”。

* 由于是正整数，和依然具有单调性。你可以维护一个和大于等于 target 的窗口，不断尝试收缩以寻找最小长度。

长度为 K 的子数组的最大和/乘积：

* 这是一个固定大小的滑动窗口。不需要动态收缩，只需要每次移动一步：加上新元素，减去最旧的元素。

如果数组包含 0 或负数怎么办？

* 这就破坏了单调性。乘积可能会在加入负数时变小，或者遇到 0 变为 0。

* 此时简单的滑动窗口可能会失效。这种情况下，通常需要结合哈希表或者前缀积来处理，或者需要更复杂的逻辑分段处理。这也是面试中常见的追问点（Follow-up），考察你对算法适用条件的理解。

—

8. 总结

在这篇文章中，我们深入探讨了“乘积小于 K 的子数组”这一经典问题。

我们从简单的暴力解法出发，发现了性能瓶颈；随后利用正整数乘积的单调性，引入了滑动窗口这一强有力的工具，将时间复杂度从 $O(N^2)$ 优化到了 $O(N)$。我们不仅提供了完整的 C++ 代码实现，还深入剖析了“以 right 结尾的子数组个数”这一核心统计逻辑，并讨论了边界条件的处理。

关键要点回顾：

单调性是滑动窗口的前提：确认数据变化规律是单调递增或递减。
双指针协作：一个指针负责探索（INLINECODE55c46632），一个指针负责维护条件（INLINECODE8f272a64）。
数学统计转换：将“全局计数”转化为“局部计数（窗口长度）”是解题的关键。

希望这次详细的解析能帮助你彻底掌握滑动窗口技巧。不妨现在就打开你的编译器，亲手实现一下代码，感受一下算法运行时那种行云流水般的顺畅感吧！

投稿给我们	如何建站？
vps是什么？	如何安装宝塔？
如何通过博客赚钱？	便宜wordpress托管方案
免费wordpress主题	这些都是免费方案

豆丁博客