Java 滑动窗口难点突破：「乘积小于 K 的子数组」的计数技巧

问题背景

给定正整数数组 nums 和整数 K，统计所有连续子数组中，元素乘积严格小于 K 的子数组数量。
示例：
输入：nums = [10,5,2,6], K = 100
输出：8
解释：满足条件的子数组包括：[10], [5], [2], [6], [5,2], [2,6], [5,2,6], [10,5]

---

核心难点

1. 暴力解法失效：枚举所有子数组的时间复杂度为 $$O(n^2)$$，当 $$n \geq 10^4$$ 时会超时。
2. 乘积非单调性：数组含正整数时，扩大窗口可能使乘积突然溢出（如遇到大数），需动态调整边界。
3. 计数去重：如何避免重复统计子数组？

---

滑动窗口解法

核心思想：

• 维护窗口 [left, right]，确保窗口内乘积 $$ \prod < K $$。
• 当窗口满足条件时，以 right 结尾的子数组数量 = right - left + 1。

算法步骤：

1. 初始化 left = 0, product = 1, count = 0。
2. 遍历 right（从 0 到 n-1）：
   • 更新乘积：product *= nums[right]。
   • 当 product >= K 时，右移 left 并缩小乘积：product /= nums[left++]。
   • 累加以 right 结尾的有效子数组数量：count += (right - left + 1)。

数学原理：
若窗口 [left, right] 满足 $$ \prod_{i=left}^{right} \text{nums}[i] < K $$，则：

• 所有以 right 结尾的子数组 [x, right]（其中 $$x \in [left, right]$$）均满足条件。
• 此类子数组数量为 $$(right - left + 1)$$。

---

代码实现

public int numSubarrayProductLessThanK(int[] nums, int k) {
    if (k <= 1) return 0; // 处理边界
    int left = 0, product = 1, count = 0;
    for (int right = 0; right < nums.length; right++) {
        product *= nums[right];
        while (product >= k) { // 收缩窗口
            product /= nums[left++];
        }
        count += (right - left + 1); // 关键计数
    }
    return count;
}

关键点解析：

1. 边界处理：当 K <= 1 时无解（正整数乘积最小为 1）。
2. 窗口收缩：while 确保窗口内乘积始终 $$< K$$。
3. 高效计数：直接计算以 right 结尾的子数组数量，避免重复扫描。

---

复杂度分析

• 时间复杂度：$$O(n)$$，每个元素最多被访问两次（加入/移除窗口）。
• 空间复杂度：$$O(1)$$，仅用常数变量。

---

实战案例

以 nums = [10,5,2,6], K = 100 为例：

right	left	窗口	乘积	新增子数组数量
0	0	[10]	10	0-0+1 = 1
1	0	[10,5]	50	1-0+1 = 2
2	0	[10,5,2]	100 → 收缩窗口
2	1	[5,2]	10	2-1+1 = 2
3	1	[5,2,6]	60	3-1+1 = 3
累计：1 + 2 + 2 + 3 = 8

---

总结

1. 核心技巧：利用「以右端点结尾的子数组数量」公式 $$(right - left + 1)$$ 实现高效计数。
2. 适用场景：连续子数组的乘积/和问题（数组元素为正整数）。
3. 思维延伸：若含负数或零，需结合前缀和与哈希表处理，但本题约束简化了问题。

掌握此技巧后，类似问题如「和小于 K 的子数组」均可举一反三！