线性动态规划：乘积小于K的子数组个数（进阶版——支持负数与零）

一、问题描述

给定一个整数数组 nums 和一个整数 k，求该数组中所有元素乘积严格小于 k 的连续子数组的个数。
进阶条件：数组元素可能包含负数、零和正数，而不仅仅是正数。

示例：

• 输入：nums = [10, 5, 2, 6], k = 100
  输出：8
  解释：所有乘积小于100的连续子数组为：
  [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]（注意[10,5,2]乘积为100，不小于100，不计入）

• 输入：nums = [-2, 1, -3], k = 0
  输出：4
  解释：乘积小于0的连续子数组为：[-2], [-2, 1], [1, -3], [-3]（注意负数乘积可能小于零）

二、基础情况（数组元素均为正整数）

如果数组元素均为正整数，问题较为简单，可以用滑动窗口解决：

1. 思路：
   固定窗口右端点 right，不断移动左端点 left，使得窗口内乘积 < k。
   对于每个 right，满足条件的子数组个数为 right - left + 1（即包含 nums[right] 且乘积 < k 的子数组数量）。

2. 算法步骤：

   • 初始化 left = 0, product = 1, count = 0。
   • 遍历 right 从 0 到 n-1：
     • product *= nums[right]。
     • 当 product >= k 且 left <= right 时，不断将 nums[left] 从乘积中除掉，left++。
     • 如果 product < k，则当前窗口内所有以 nums[right] 结尾的子数组乘积都 < k，数量为 right - left + 1，累加到 count。
   • 返回 count。

3. 举例：nums = [10, 5, 2, 6], k = 100

   • right=0：乘积=10，left=0，个数=1（[10]）
   • right=1：乘积=50，个数=2（[5], [10,5]）
   • right=2：乘积=100 → 移除10，乘积=10，left=1，个数=2（[2], [5,2]）
   • right=3：乘积=60，个数=3（[6], [2,6], [5,2,6]）
     总和 = 1+2+2+3 = 8。

三、进阶情况（数组包含负数与零）

当数组包含负数与零时，乘积的正负会随窗口内负数个数变化，且遇到零时乘积归零。
关键难点：乘积可能突然变为零，滑动窗口缩小到零之后乘积仍为零，无法直接恢复。

步骤1：分解问题——以零为分割点

由于任何包含零的子数组乘积为零，若 k > 0，则包含零的子数组乘积为0 < k，是有效的；但零会打断连续乘积的计算。
技巧：将数组按零分割成若干个不含零的连续子数组，分别对每个子数组计算乘积 < k 的子数组数，最后加上包含零的子数组。

例如：nums = [2, -1, 0, 3, -2], k=5
分割为：[2, -1] 和 [3, -2] 两段，分别计算，最后单独处理包含零的子数组。

步骤2：对不含零的段进行处理（允许负数）

对于一个不含零的段，设其长度为 m。
由于乘积的正负会变化，传统的滑动窗口不能直接用。但我们可以用前缀乘积结合二分查找或双指针变形。

方法A：前缀乘积 + 二分查找（适用于任意k）

• 计算前缀乘积数组 prefix，其中 prefix[i] 表示前 i 个元素的乘积（prefix[0]=1）。
• 对于每个右端点 right，我们需要找到最小的 left 使得 prefix[right+1] / prefix[left] < k。
• 由于有负数，乘积不是单调的，不能直接二分。但可以对前缀乘积取对数，将乘法转为加法，并记录下标，但这涉及到浮点数误差。

方法B：双指针的扩展——记录最大乘积和最小乘积
实际上是乘积最大子数组的变体，不太适合计数问题。

方法C：分段后，用滑动窗口控制乘积绝对值
对于一个不含零的段，如果 k>0，我们希望乘积 < k。但负数乘积可能很小，而我们需要的是乘积的绝对值吗？不，我们需要的是乘积 < k，而不是绝对值。
因此，我们可以分别计算乘积为正且 < k 和乘积为负的子数组数，但比较复杂。

步骤3：更通用解法——前缀乘积 + 双指针变形（处理负数）

对于一个不含零的段，用两个指针 left 和 right 维护窗口，但乘积可能为负。
我们可以维护窗口内乘积的绝对值吗？不能，因为乘积的正负会影响与 k 的比较。

技巧：

1. 如果 k > 0，那么乘积 < k 有两种情况：

   • 乘积为正且 < k
   • 乘积为负（一定 < k，因为负数小于正数 k）
     所以，只要乘积不为正且绝对值很大，就一定 < k 吗？不对，比如 k=5，乘积为 -10，虽然为负，但绝对值大于k，但仍然 < k 吗？
     是的，因为 -10 < 5 成立。
     所以对于 k>0，任何负数乘积都满足条件，正数乘积需要 < k。

2. 如果 k <= 0，

   • 若 k=0，需要乘积 < 0 或乘积为负？不对，乘积 < 0 才满足条件。
   • 若 k<0，如 k=-5，需要乘积 < -5，负数乘积可能更小，正数乘积都大于等于0，不满足条件。

因此，情况变得复杂。一个通用方法是：

步骤4：通用解法——滑动窗口记录乘积符号和绝对值

维护一个窗口，使得窗口内乘积的绝对值 < |k| 且乘积符号满足与 k 的大小关系。
具体地，对于当前窗口乘积 prod：

• 如果 prod == 0，则重置窗口（因为段内无零，不会发生）。
• 用变量 sign 记录乘积符号（1为正，-1为负）。
• 用变量 absProd 记录乘积绝对值（用对数转换为和的形式避免溢出）。

但这样实现复杂，且在计数时需小心。

步骤5：实际可行的简化思路（处理零）

1. 将数组按零拆分成若干段无零子数组。

2. 对每段无零子数组，用滑动窗口计算乘积 < k 的连续子数组数，但需注意负数乘积的处理：

   • 对于 k > 0：
     负数乘积总是 < k，正数乘积需 < k。
     我们可以用双指针，保证窗口内乘积的绝对值 < k 且乘积为正时，满足 < k 才计数，但实际上这样做很绕。

   • 一个简单方法：
     用前缀乘积，对每个右端点，找到最小的左端点，使得乘积 < k。
     由于乘积有正负，前缀乘积不是单调的，但我们可以用双指针控制：
     当乘积绝对值 >= |k| 时，移动左指针。但乘积可能为负且绝对值很大，仍然满足 < k，所以不能仅靠绝对值。

3. 因此，一个实用的工程方法是：

   • 遍历右端点 right，同时记录当前乘积。
   • 如果当前乘积的绝对值 >= |k| 且乘积为正，则需要缩小窗口直到乘积 < k。
   • 如果乘积为负，则即使绝对值很大，也满足 < k（当 k>0 时）。
   • 如果 k<=0，则只有负数乘积才可能 < k，且需满足乘积 < k（更小的负数）。

步骤6：最终算法步骤

1. 如果 k <= 0，则只有负数乘积才可能 < k，且乘积必须小于 k（负数更小）。但若 k=0，则需乘积 < 0。
   实际上，这种情况较为少见，我们可单独处理 k<=0 的情况。

2. 更通用的实现：

   • 用双指针 i 和 j 表示窗口左右。
   • 维护窗口内乘积 prod。
   • 当 prod >= k 且 prod > 0 时，移动左指针缩小窗口。
   • 如果窗口内乘积为负，则即使绝对值大，也满足 < k（当 k>0）。
   • 计数时，如果当前乘积 < k，则累加 j-i+1 表示以 nums[j] 结尾的子数组数。
     但这样在遇到负数时，乘积符号会变化，需要额外处理。

3. 由于这样实现较为复杂，竞赛中常见的做法是：

   • 如果 k <= 0，直接特判：
     • 若 k=0，计数所有乘积为负的子数组。
     • 若 k<0，计数所有乘积 < k 的子数组（需遍历所有子数组，用前缀乘积+哈希记录符号和值）。
   • 如果 k > 0，用滑动窗口，维护乘积的绝对值 < k 且乘积为正时，需保证乘积 < k，否则不缩小窗口。

四、总结

对于全为正数的情况，直接用滑动窗口。
对于含负数与零的情况，一种可行方案是：

1. 如果 k > 0，将数组按零拆分成段，对每段：
   • 用滑动窗口，维护窗口内乘积的绝对值 < k，同时记录乘积符号。
   • 当乘积为正且绝对值 >= k 时，移动左指针。
   • 每步累加以右端点结尾的满足条件的子数组数。
2. 如果 k <= 0，则需单独处理负数乘积，可枚举所有子数组或使用前缀乘积+符号记录，复杂度较高。

五、代码框架（C++，k>0 且含负数与零）

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if (k <= 0) return 0; // 这里假设 k>0 简化处理
    int n = nums.size();
    int count = 0;
    for (int i = 0; i < n; ) {
        if (nums[i] == 0) {
            i++; // 零会在后续单独计算
            continue;
        }
        int j = i;
        long long prod = 1;
        int left = i;
        while (j < n && nums[j] != 0) {
            prod *= nums[j];
            while (prod >= k && left <= j) {
                prod /= nums[left];
                left++;
            }
            count += (j - left + 1);
            j++;
        }
        i = j;
    }
    // 补充包含零的子数组数
    // 如果 k > 0，则包含零的子数组乘积为0 < k，都有效
    // 这部分可通过计算每个零所在的连续段来计数
    // 简化：所有包含至少一个零的子数组数 = 总子数组数 - 不包含零的子数组数
    // 但更简单：单独计算每个零的贡献
    int zeroCount = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] == 0) {
            int left = i;
            while (i < n && nums[i] == 0) i++;
            int len = i - left;
            zeroCount += len * (len + 1) / 2; // 连续零段的子数组数
        }
    }
    count += zeroCount;
    return count;
}

注意：上述代码是简化版本，仅处理 k>0 且将零单独计算。对于 k<=0 的情况，需另外实现。

希望这个分步讲解帮助你理解了乘积小于K的子数组个数的进阶问题。如果你有疑问，可以针对具体步骤深入探讨。